52 lines
1.1 KiB
C++
52 lines
1.1 KiB
C++
#include <iostream>
|
||
#include <algorithm>
|
||
#include <vector>
|
||
using namespace std;
|
||
//int ax[] = {1, 2, 4, 8, 9};
|
||
|
||
//按照分布，检查是否能够排列即可
|
||
/*
|
||
1、读入arr, mid
|
||
2、按照分布排列，找到离mid格最近的槽位插入
|
||
*/
|
||
int check(const vector<int>& arr, int mid){
|
||
if(arr.empty()) return 0;
|
||
|
||
int cnt = 1;
|
||
int n = arr.size();
|
||
int dist = 0;
|
||
for(int i = 1; i < n; ++i){
|
||
dist += arr[i] - arr[i - 1];
|
||
if(dist >= mid){
|
||
cnt++;
|
||
dist = 0;
|
||
}
|
||
}
|
||
return cnt;
|
||
}
|
||
|
||
int main(){
|
||
int n = 5, c = 3;
|
||
cin >> n >> c;
|
||
vector<int> arr(n);
|
||
for(int i = 0; i < n; i++){
|
||
cin >> arr[i];
|
||
//arr[i] = ax[i];
|
||
}
|
||
sort(arr.begin(), arr.end());
|
||
int smin = 0, smax = arr.back() - arr.front();
|
||
//range [smin, smax], do mid to this range
|
||
int l = smin, r = smax;
|
||
int ans = 0;
|
||
while(l <= r){
|
||
int mid = (l+r)/2;
|
||
int cc = check(arr, mid);
|
||
if (cc >= c) {
|
||
ans = mid;
|
||
l = mid + 1;
|
||
} else r = mid - 1;
|
||
}
|
||
cout << ans << endl;
|
||
return 0;
|
||
}
|