题面
E. Convention
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Cows from all over the world are arriving at the local airport to attend the convention and eat grass. Specifically, there are NN cows arriving at the airport (1≤N≤1051≤N≤105) and cow ii arrives at time titi (0≤ti≤1090≤ti≤109). Farmer John has arranged MM (1≤M≤1051≤M≤105) buses to transport the cows from the airport. Each bus can hold up to CC cows in it (1≤C≤N1≤C≤N). Farmer John is waiting with the buses at the airport and would like to assign the arriving cows to the buses. A bus can leave at the time when the last cow on it arrives. Farmer John wants to be a good host and so does not want to keep the arriving cows waiting at the airport too long. What is the smallest possible value of the maximum waiting time of any one arriving cow if Farmer John coordinates his buses optimally? A cow’s waiting time is the difference between her arrival time and the departure of her assigned bus.
It is guaranteed that MC≥NMC≥N.
Input
The first line contains three space separated integers NN, MM, and CC. The next line contains NN space separated integers representing the arrival time of each cow.
Output
Please write one line containing the optimal minimum maximum waiting time for any one arriving cow.
Example
【R1_E_Convention】input
6 3 2
1 1 10 14 4 3
output
4
题目大意
给定一个长度为N的序列，分成几个子序列（可以不连续），这几个子序列的长度不超过C，子序列的个数最多为M，询问如何划分使得这几个子序列的极差（子序列中最大值减最小值）的最大值最小。
题目分析
看到使得最大值最小，我们很容易想到二分中一个很经典的问题，最小化最大值。思路就是排序+贪心，然后二分枚举答案。从一个很大的值折半查询，看这个答案能不能成立。所以代码的关键就是这个判别函数的书写。假设最大值为 d d d，我们先确定一个起始点 n o w now now，然后 n e x t = n o w + C ? 1 next = now+C - 1 next=now+C?1确定结尾，划分好子序列。然后计算这个子序列的极差，是否超过我们设定的 d d d，超过的话, n e x t ? ? next-- next??。若 n e x t = n o w next = now next=now的话，肯定是符合极差小于 d d d这个条件的。接下来就是 n o w = n e x t + 1 now = next + 1 now=next+1确定下一个子序列的开头，进行循环。终止条件就是划分子序列的个数达到 M M M或者 n o w = N now=N now=N就可以退出循环了。若是最后$now \ne N $那么说明这个最大值不能满足，返回
false。而且这里有个小坑，因为是最小化最大值，所以返回的是右边的值，而且要先判断0是否可行，可行的话直接返回0。
代码
#include
#include
using namespace std;
const int maxn = 1e5 + 7;
int arr[maxn];
int N, M, C;
int mx = -1;
bool judge(int d){
int now = 0;
for(int i = 0;
i < M && now < N;
i++){
int next = (now + C >= N? N - 1: now + C - 1);
while(arr[next] - arr[now] > d)next--;
now = next + 1;
if(i == M - 1 && now != N) return false;
}
return true;
}
int solve(void){
sort(arr, arr + N);
if(judge(0)) return 0;
int l = 0, r = mx;
while(r - l > 1){
int mid = (l + r) / 2;
if(judge(mid)) r = mid;
else l = mid;
}
return r;
}
int main(int argc, char const *argv[]) {
scanf("%d%d%d", &N, &M, &C);
for(int i = 0;
i < N;
i++){
scanf("%d", &arr[i]);
mx = max(mx, arr[i]);
}
sort(arr, arr + N);
printf("%d\n", solve());
return 0;
} 
