|
|
思路：
首先對(duì)所有位置排序一下。
可能的最大的 distance 為 (range_right - range_left) / (C - 1)。
所以二分答案的時(shí)候區(qū)間的右邊就是這個(gè)了。
判斷某個(gè) distance 是否能夠成立的過(guò)程很簡(jiǎn)單：
只需要從左往右放牛，如果放到最后一個(gè)點(diǎn)都放不完，就不成立了。
代碼 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;
}
|