题意

题目背景

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

题目描述

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有\(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\)。

思路

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

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

考虑二分答案。对于每次二分出的答案，我们来判断至少需要拆除多少石头，那么这就是个常数十分之小的\(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;

}

石头

Luogu P2678 跳石头(二分)

题意