در کشور شانگالیا مردم برای هر کاری باید مالیات بپردازند. در این کشور یک نانوایی وجود دارد که وقتی شروع به پخت می‌کند از قبل افراد پشت درب آن صف کشیده‌اند و فقط به کسانی نان می‌دهد که قبل از شروع پخت در صف ایستاده باشند. امروز در ابتدای پخت ‎$n$‎ نفر در صف حضور دارند که نفر ‎$i$‎ام ‎$a_i$‎ قرص نان می‌خواهد. نانوایی با شروع از زمان صفر، در پایان هر دقیقه یک نان تحویل می‌دهد. اگر نفر ‎$i$‎ام در لحظه‌ی ‎$t$‎ همه‌ی نان‌های خود را بگیرد باید ‎$t\times a_i$‎ سِلار مالیات بپردازد (سِلار واحد پولی شانگالیاست). افراد می‌خواهند به گونه‌ای در صف بایستند که مجموع مالیات پرداختی توسط آن‌ها کمینه شود. الگوریتمی برای این کار ارائه کنید که با دریافت ‎$a_i$‎ها، ترتیب بهینه و مجموع مالیاتی را که افراد می‌بایست بپردازند مشخص کند. الگوریتم شما باید از زمان اجرای ‎$O(n)$‎ باشد. درستی آن را اثبات کنید.

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