حل تمرین آب کوئرا با پایتون

حل تمرین آب کوئرا با پایتون

در این نوشته به روش حل یکی از سوالات پیاده سازی برنامه نویسی وب‌سایت کوئرا می‌پردازیم.

حل تمرین آب کوئرا با پایتون

شهر مقدّس آنیتا در یونان باستان شهری بود که تمام ساختمان­‌های آن در یک ردیف ساخته شده بود. با وجود قدیمی بودن، این شهر از ساختمان­‌های بلند ساخته شده بود و همچنین عرض هر ساختمان در این شهر دقیقا 1 متر بود. نقل است که در این شهر، به هنگام بارش باران آب تا جای ممکن بر روی ساختمان­‌ها جمع می­‌شود. در واقع اگر این شهر را روی یک خط از راست به چپ در نظر بگیریم، آب جمع شده روی ساختمان‌­ها فقط از راست و چپ می­‌ریخت. در یونان قدیم، یک سال کامل باران آمد. می‌خواهیم ببینیم در این صورت روی سقف ساختمان‌­های آنیتا حداکثر چه مقدار آب جمع شده است.

ورودی

در سطر اول ورودی عدد طبیعی n (تعداد ساختمان‌ها) آمده است. در سطر بعد n عدد آمده است که به ترتیب ارتفاع ساختمان‌ها را از راست به چپ مشخص می‌کنند و با فاصله از هم جدا شده‌اند. ارتفاع هر ساختمان حداکثر 1000 متر خواهد بود.

خروجی

در تنها خط خروجی حداکثر میزان آب جمع شده روی سقف ساختمان‌های شهر آنیتا (بر حسب متر مربّع) بنویسید.

مثال

ورودی نمونه 1

7
4 1 3 5 2 3 4

خروجی نمونه 1

7

کد پایتون سوال تمرین آب

n = int(input())
heights = list(map(int, input().split()))
left_max = [0] * n
right_max = [0] * n
left_max[0] = heights[0]

for i in range(1, n):
    left_max[i] = max(left_max[i - 1], heights[i])

right_max[n - 1] = heights[n - 1]
for i in range(n - 2, -1, -1):
    right_max[i] = max(right_max[i + 1], heights[i])

water_trapped = 0
for i in range(n):
    # Water trapped at current building is min(left_max[i], right_max[i]) - heights[i]
    water_trapped += min(left_max[i], right_max[i]) - heights[i]

print(water_trapped)

منبع سوال: کوئرا

اگر نیاز به حل تمرین‌های دیگری از کوئرا دارید در بخش نظرات همین نوشته برای ما بنویسید.