题意

题目背景

一年一度的“跳石头”比赛又要开始了!

题目描述

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有(N)块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走(M)块岩石（不能移走起点和终点的岩石）。

输入输出格式

输入格式：

第一行包含三个整数(L,N,M)，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证(L geq 1)且(N geq M geq 0)。

接下来(N)行，每行一个整数，第(i)行的整数(D_i(0<D_i<L))，表示第(i)块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

输出格式：

一个整数，即最短跳跃距离的最大值。

输入输出样例

输入样例：

输出样例：

说明

输入输出样例(1)说明：将与起点距离为(2)和(14)的两个岩石移走后,最短的跳跃距离为(4)(从与起点距离(17)的岩石跳到距离(21)的岩石,或者从距离(21)的岩石跳到终点)。

另：对于(20 \%)的数据,(0 leq M leq N leq 10)。

对于(50 \%)的数据,(0 leq M leq N leq 100)。

对于(100 \%)的数据,(0 leq M leq N leq 50,000, 1 leq L leq 1,000,000,000)。

思路

卧槽czk又是(rank 1)。 --alecli

最近一直在学二分答案呢，发现有不少的题目都可以用二分答案来解决。

这题一开始想到的是贪心，拆去所有距离最近的石头，不过这就要枚举拆除哪一块石头，时间复杂度难以保证。~~除非我们使用模拟退火算法。~~

考虑二分答案。对于每次二分出的答案，我们来判断至少需要拆除多少石头，那么这就是个常数十分之小的(O(n log n))算法，可以完美解决这一题。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e4+5;
int l,n,m,L,R,ans,a[MAXN],b[MAXN];
int read()
{
    int re=0;
    char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) re=(re<<3)+(re<<1)+ch-'0',ch=getchar();
    return re;
}
bool check(int dis)
{
    int re=0;
    for(int i=1;i<=n;i++) b[i]=a[i];
    for(int i=1;i<=n;i++)
        if(b[i]-b[i-1]<dis)
            re++,b[i]=b[i-1];
    return re<=m;
}
int main()
{
    l=read(),n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    a[++n]=l;
    L=1,R=l;
    while(L<=R)
    {
        int mid=(L+R)>>1;
        if(check(mid)) ans=mid,L=mid+1;
        else R=mid-1;
    }
    printf("%d",ans);
    return 0;
}