در یک کشور $n$ شهر وجود دارد که در هر یک از آن‌ها یک منبع آب قرار دارد. در بین برخی از شهرها جاده‌‏هایی ایجاد شده است که راه‌های ارتباطی این شهرها را تشکیل می‌دهد، در ضمن پیمودن هر جاده که بین دو شهر ایجاد شده است یک روز طول می‌کشد. در هر شهر تعدادی آدم زندگی می‌کند. در یک عملیات خرابکارانه منابع آب همه شهرها سوراخ می‌شود. می‌دانیم در ابتدای کار در منبع شهر $i$ام $v_i$ متر مکعب آب وجود دارد و بعد از سوراخ شدن منبع‌ها در هر روز یک مترمکعب از آب هر منبع کم می‌شود. ما شهرها را به ترتیب صعودی میزان آب اولیه‌شان داریم. ساکنین همه‌ی شهرها بعد از این اتفاق تصمیم به مهاجرت می‌گیرند (ممکن است تصمیم بگیرند در شهر خود بمانند). ساکنین یک شهر مقصد خود را شهری انتخاب می‌کنند که در زمان رسیدن به آن شهر منبع‌ آبش بیشترین آب را داشته باشد. اگوریتمی از $Ο(n+m)$ که $n$ تعداد شهرها و $m$ تعداد جاده‌هاست ارائه دهید که مقصد مردم هر شهر را بیابد ($v_i$ها عدد صحیح هستند).

• سوال بعد
• سوال قبل