[luogu-2678]noip2015day2-T1 跳石头 题解

题意解析：题目就是给了你n个在数轴上的点，然后还有起点和终点，坐标分别为0和n，然后去掉最多m个点（除了起点和终点），使剩下的点两两距离的最小值最大。

My opinion：这题唯一的问题是去掉的点不一定要取满m，只需要最后的最小值最大就行了，这时候如果我们知道答案的话，我们就可以判断，这个答案是否可行，而且如果x答案可行，那么x-1一定可行，如果x不可行，x+1一定不可行。所以可以使用二分答案法来寻找答案。 总结： 1、输入。 2、把答案从0到L二分。 3、判断这个答案是否可行。

神奇的代码：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define Clear(a,x) memset(a,x,sizeof(a))
#define ll long long
#define INF 2000000000
#define eps 1e-8
using namespace std;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<0||ch>9) f=ch==-?-1:f,ch=getchar();
    while (ch>=0&&ch<=9) x=x*10+ch-0,ch=getchar();
    return x*f;
}
const int maxn=50005;
int d[maxn],a[maxn];
int L,n,m;
bool ok(int k){
    int last=0,num=0;
    rep(i,1,n+1){
        if (d[i]-last<k) num++;
            else last=d[i];
        if (num>m) return false; 
    }
    return true;
}
int main(){
    L=read(),n=read(),m=read();
    rep(i,1,n) d[i]=read();
    d[0]=0,d[n+1]=L;
    int l=0,r=L;
    while (l<r){
        int mid=(l+r+1)>>1;
        if (ok(mid)) l=mid;
            else r=mid-1;
    }
    printf("%d
",l);
    return 0;
}