Masala #GALHNL4E9B
Mashinalarni yo'l bo'ylab taqsimlash
Bir yo‘l bo‘ylab n ta manzil (stansiya) joylashgan, ularning masofalari x[1], x[2], ..., x[n] ko‘rinishida berilgan (0 dan boshlanadi, masofalar ortib boruvchi tartibda). Sizda k ta mashina bor. Har bir mashina o‘ziga biror ketma-ket stansiyalar guruhini olish kerak.
Mashinaning masofasi — unga biriktirilgan bo‘lakdagi oxirgi va birinchi stansiya orasidagi masofa (ya’ni segment uzunligi). Siz mashinalar orasida bu maksimal masofani imkon qadar kichraytirishingiz kerak.
Boshqacha qilib aytganda, siz n stansiyani ketma-ket k bo‘lakka ajratasiz, va bo‘laklarning eng kattasi minimal bo‘lishi kerak.
- Birinchi qatorda ikkita butun son nvak(1 ≤ k ≤ n ≤ 2·10^5).
- Ikkinchi qatorda nta butun sonx[1], x[2], ..., x[n](0 ≤ x[i] ≤ 10^9, vax[1] < x[2] < ... < x[n]).
Bitta butun son — mashinalar taqsimotida eng katta segment uzunligining minimal qiymati.
| # | input.txt | output.txt | 
|---|---|---|
| 1 | 5 2 0 3 7 10 14 | 7 | 
| 2 | 7 3 1 2 6 7 11 14 18 | 5 | 
1-test. Agar [0,3,7] va [10,14] ga bo‘lsak, segment uzunliklari 7 va 4, maksimal = 7. Bu minimal holat.
2-test. Bo‘lish [1,2], [6,7,11], [14, 18] → segment uzunliklari 1,5,4, maksimal = 5. Bundan kichik qilishning imkoni yo‘q.
 Telegram kanalimizga obuna bo'ling
 Telegram kanalimizga obuna bo'ling