Masala N
Robotlar Poygasi
"Kiber-Olimp" musobaqasida sizning jamoangizga N ta vazifadan iborat topshiriq kelib tushdi. Musobaqa shartiga ko'ra, jamoa N ta vazifani bajarishi kerak. Har bir vazifani bajarish uchun ma'lum bir T[i] vaqt kerak bo'ladi. Sizda bu vazifalarni bajarish uchun M ta robot mavjud.
Robotlarning ishlash prinsipi quyidagicha: Vazifalar ro'yxatda qanday tartibda kelgan bo'lsa, ularni xuddi shu ketma-ketlikni buzmagan holda robotlarga taqsimlash kerak. Ya'ni, birinchi robot ro'yxat boshidan boshlab ketma-ket bir nechta vazifani oladi. Ikkinchi robot esa birinchi robot ishini tugatgan vazifaning keyingisidan boshlab o'ziga vazifalarni oladi va hokazo. Hech bir robot vazifalarni tanlab yoki o'rnini almashtirib ola olmaydi.
Sizning vazifangiz — vazifalarni robotlar o'rtasida shunday taqsimlash kerakki, eng ko'p ish vaqt sarflagan (eng band bo'lgan) robotning umumiy ish vaqti imkon qadar minimal bo'lsin.
Kiritish: Birinchi qatorda N (1≤N≤10^5) va M (1≤M≤10^5). Ikkinchi qatorda N ta butun son: T[1], ..., T[N] (1≤T[i]≤10^9).
Minimal mumkin bo'lgan maksimal ish vaqti.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
7 3 8 4 7 5 6 3 2 |
12 |
Maqsadimiz — vazifalarni 3 ta robotga shunday taqsimlashki, eng ko'p ishlagan robotning umumiy ish vaqti imkon qadar kam bo'lsin. Javob 12. Keling, nima uchun aynan 12 ekanligini ko'rib chiqamiz.
Biz har bir robotning ish vaqtini 12 dan oshirmasdan barcha vazifalarni taqsimlay olamiz. Mana bir misol taqsimot:
- 1-robot:
8va4vaqtli vazifalarni oladi. Umumiy ish vaqti:8 + 4 = 12. - 2-robot:
7va5vaqtli vazifalarni oladi. Umumiy ish vaqti:7 + 5 = 12. - 3-robot:
6,3va2vaqtli vazifalarni oladi. Umumiy ish vaqti:6 + 3 + 2 = 11.
Telegram kanalimizga obuna bo'ling