poj 2456 Aggressive cows
程序员文章站
2022-06-17 20:24:35
...
题目:
首先把牛棚的位置x[i]按从小到大排序。牛棚数量N,牛数量为C,则每两只牛间可能的最大距离r=(x[N - 1] - x[0]) / (C - 1)。用二分法搜索0~r,判断mid满不满足条件。
AC情况:
代码:
#include<iostream>
#include<algorithm>
using namespace std;
int x[100005];
int N, C;
int main() {
scanf("%d%d", &N, &C);
for (int i = 0; i < N; i++)
scanf("%d", &x[i]);
sort(x, x + N);
int l = 1, r = (x[N - 1] - x[0]) / (C - 1);
while (r - l > 1) {
int mid = (l + r) / 2, ans = 0;
for (int i = 0; ans < C&&i < N;) {
int t = i;
while (x[++i] - x[t] < mid);
ans++;
}
if (ans >= C)
l = mid;
else
r = mid;
}
if (l != r) {
int ans = 0;
for (int i = 0; ans < C&&i < N;) {
int t = i;
while (x[++i] - x[t] < r);
ans++;
}
if (ans >= C)
l = r;
}
printf("%d\n", l);
return 0;
}