Kiruvchi ma’lumotlar

4-Topshiriq

To’g’richiziqbo’ylabntaustunjoylashganbo’lib, ulargaktasigirnibog’lashlozim. Ularni ustunlarga shunday bog’lash kerakki sig’irlar orasidagi minimal masofa eng iloji boricha eng katta bo’lsin.

Kiruvchi ma’lumotlar

Birinchi qatorda n – ustunlar soni va k – sig’irlar soni beriladi(3≤n≤10000, 2≤k<n). Keyingi qatorda n ta natural son – ustunlar koordinatalari o’sish tartibida beriladi va 10⁹ dan oshmaydi.

Chiquvchi ma’lumotlar

Bitta butun sonni – masalaning javobini chiqaring.

Misollar

№	Kiruvchi ma’lumotlar	Chiquvchi ma’lumotlar
1	5 3 1 2 3 100 1000	99

Masalaning yechimi

#include

#define int long long

using namespace std;

int k;

int tekshr(int a[], int n, int num){

int cnt = 1, t = a[1];

for (int i = 2; i <= n; i++){

if (a[i] - t >= num){

cnt++;

t = a[i];

if (cnt == k)

return 1;

}

}

return 0;

}

int bin_search(int a[], int n){

int l = 1, r = a[n], mx = INT_MIN;

while (r > l){

int mid = (l + r) / 2;

if (tekshr(a, n, mid) == 1){

if (mid > mx)

mx = mid;

l = mid + 1;

}

else

r = mid;

}

return mx;

}

main(){

int n;

cin >> n >> k;

int a[n + 1];

for (int i = 1; i <= n; i++){

cin >> a[i];

}

int k = 1, b[n + 1];

cout << bin_search(a, n);


}