Masala #GALHNL4E9B

Xotira 32 MB Vaqt 1000 ms Qiyinchiligi 35 %

#Binar qidiruv

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.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son n va k (1 ≤ k ≤ n ≤ 2·10^5).
Ikkinchi qatorda n ta butun son x[1], x[2], ..., x[n] (0 ≤ x[i] ≤ 10^9, va x[1] < x[2] < ... < x[n]).

Chiquvchi ma'lumotlar:

Bitta butun son — mashinalar taqsimotida eng katta segment uzunligining minimal qiymati.

Misollar

#	input.txt	output.txt
1	5 2 0 3 7 10 14	7
2	7 3 1 2 6 7 11 14 18	5

Izoh:

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 Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin