|
|
思路：
首先对所有位置排序一下。
可能的最大的 distance 为 (range_right - range_left) / (C - 1)。
所以二分答案的时候区间的右边就是这个了。
判断某个 distance 是否能够成立的过程很简单：
只需要从左往右放牛，如果放到最后一个点都放不完，就不成立了。
代码 140ms：
 #include <stdio.h>
#include <stdlib.h>
int N, C, in[100032];
int cmp(const void *a, const void *b)
   {
 return *(int *)a - *(int *)b;
 }
__inline int can(int val)
{
int i, pos, sum;
pos = 1;
  for (i = 1; i < C; i++) {
sum = 0;
while (pos < N && sum < val) {
sum += in[pos] - in[pos - 1];
pos++;
 }
if (sum < val)
return 0;
}
return 1;
}
int main()
{
int i, l, r, m;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &N, &C);
for (i = 0; i < N; i++)
scanf("%d", &in[i]);
qsort(in, N, sizeof(in[0]), cmp);
l = 0;
r = (in[N - 1] - in[0]) / (C - 1);
while (l <= r) {
m = (l + r) / 2;
if (can(m))
l = m + 1;
else
r = m - 1;
}
printf("%d\n", r);
return 0;
}
|