Bu masalada berilgan massivni tartibini buzmagan holda \(m\) ta ketma-ket bo'lakka bo'lishimiz va har bir bo'lak yig'indilarining eng kattasini (maksimal qismini) imkon qadar kichik qilishimiz talab etiladi.

Asosiy g'oya (Binary Search on Answer):

Massiv elementlari va o'lchami katta bo'lgani uchun (\(\le 2 \times 10^5\)), to'g'ridan-to'g'ri qidirib chiqish vaqt chegarasiga ulgurmaydi. Shuning uchun javobning o'zini ikkilik qidiruv orqali topamiz.

1. Qidiruv chegaralari (low va high):

• Javob eng kamida massivdagi eng katta elementga teng bo'lishi shart (\(low = max(a)\)), chunki bitta elementning o'zi boshqalardan katta bo'lsa ham guruh yig'indisini o'sha qiymatdan kamaytirib bo'lmaydi.
• Eng ko'pi bilan barcha elementlar yig'indisiga teng bo'lishi mumkin (\(high = sum(a)\)).

2. Ochko'zlik (Greedy) yondashuvi:

Ikkilik qidiruv orqali o'rtadagi qiymatni (\(mid\)) eng katta ruxsat etilgan limit deb olamiz. Keyin massivni chapdan o'ngga qarab yig'ib chiqamiz:

• Agar joriy elementni qo'shganda limitdan oshib ketsa, demak yangi yordamchiga o'tamiz (bo'laklar sonini \(1\) taga oshiramiz).
• Agar oxirida hosil bo'lgan bo'laklar soni \(m\) tadan oshib ketmasa, demak bu limitimiz to'g'ri keladi va javobni kichikroq tomonga qarab qidirib ko'ramiz (\(high = mid - 1\)). Aks holda limitni kattalashtiramiz (\(low = mid + 1\)).

Murakkablik

Ikkilik qidiruv taxminan \(O(\log(\text{sum}(a)))\) marta takrorlanadi.
Har bir tekshirish (greedy o'tish) \(O(n)\) vaqt oladi.
Umumiy murakkablik: \(O(n \times \log(\text{sum}(a)))\).