题目链接:https://vjudge.net/problem/POJ-3258
题意:
有一条河长为L,河中间有n块石头,算上开始和结尾一共n+2个,现在问去掉m块石头,问最短距离中的最大值是多少?
分析:
二分寻找一个值,使得可以移除m个石头。
code:
// #include <bits/stdc++.h>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 5e4 + 7;
const int INF = 0X3F3F3F3F;
int a[MAXN]; // 存石头的位置
int main()
{
int l, n, m;
while(scanf("%d %d %d", &l, &n, &m) != EOF)
{
int low = l; // 二分左右边界
int high = l;
a[0] = 0;
a[n+1] = l;
for(int i=1; i<=n; i++)
{
scanf("%d", &a[i]);
low = min(low, a[i] - a[i-1]); // 更新左边界,找到起始的最小左边界
}
low = min(low, a[n+1] - a[n]);
sort(a, a+n+2); // 输入无序,排为升序
while(low <= high)
{
int mid = (low+high) / 2;
int sum = 0;
int cnt = 0;
int i = 1;
while(i <= n+1) // 从第一个点遍历到最后一个点,终点
{
sum += a[i] - a[i-1]; // 两块石头之间的距离,不一定是连续的
if(sum <= mid)
{
cnt ++;
i++;
}
else
{
sum = 0;
i++;
}
}
// cnt == m, 说明当前mid的值已经可以移除m个石头
// 但是当前mid还不是可能最小值,有可能mid+1也符合条件
// 我们找的是最小值中的最大值,而不是最小值中的最小值,所以左边界应该+1
if(cnt <= m)
low = mid + 1;
else
high = mid - 1;
}
printf("%d\n", low);
}
return 0;
}