记录
22:55 2023-2-9
http://poj.org/problem?id=2456
reference:《挑战程序设计竞赛(第2版)》3.1.3 p142
Description
Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000).
His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?
Input
-
Line 1: Two space-separated integers: N and C
-
Lines 2..N+1: Line i+1 contains an integer stall location, xi
Output
- Line 1: One integer: the largest minimum distance
Sample Input
5 3
1
2
8
4
9
Sample Output
3
二分搜索，最大化最小值。
这里判断的条件C(d) = 可以安排牛的位置使得最近两头牛的距离不小于d。最小值体现在 距离 >= d (即最小值为d)
题目是要求满足C(d)的最大的d，这是最大化。(即求最大的)
这个最小值是指牛之间距离最小值，最大化是把距离最小值最大化。
比如两头牛，位置为1 3 4 5。
最小值取1 取2 都可以 都满足任意俩头牛距离大于d。
最大化就是在这俩个之间取大的那个，即2。
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAX_N 100000
typedef long long ll;
const int INF = 0x3f3f3f3f;
ll N, M;
ll L[MAX_N + 1];
bool check(int x) {
int last = 0, current = 0;
for(ll i = 1; i < M; i++) {
current = last + 1;
while (current < N && L[current] - L[last] < x) {
current++;
}
if(current == N) return false;
last = current;
}
return true;
}
void solve() {
sort(L, L + N);
int lb = 0, ub = INF;
while (ub - lb > 1) {
int mid = (lb + ub) / 2;
if(check(mid)) {
lb = mid;
} else {
ub = mid;
}
}
printf("%d\n", lb);
}
int main() {
scanf("%d %d", &N, &M);
for(ll i = 0; i < N; i++){
scanf("%lld", &L[i]);
}
solve();
}