Visit Counter
AmazingCounters.com

1、题目大意:就是给你一条线段,上面有一堆点,然后要删一些点,使得最长的相邻两点距离最短,最多删m个点
2、分析:这道题怎么做呢,其实很简单,就是一个二分答案,然后判断一下,怎么判呢,就是如果这个点和前面那个没被删的点
之间如果小于我们二分的值,就删了这个点。。
就是这样
3、代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int a[100000];
int l, n, m;
bool hehe(int st){
    int del = 0;
    int front = 0;
    for(int i = 2; i < n; i ++){
        if(a[i] - front >= st) front = a[i];
        else del ++;
    }
    if(a[n] - front < st) del ++;
    if(del <= m) return true;
    return false;
}
int main(){
    scanf("%d%d%d", &l, &n, &m);
    a[1] = 0;
    for(int i = 2; i <= n + 1; i ++){
        scanf("%d", &a[i]);
    }
    a[n + 2] = l;
    n += 2;
    int L = 1, R = l;
    while(L < R){
        int mid = (L + R) / 2;
        if(mid == L) mid ++;
        if(hehe(mid)) L = mid;
        else R = mid - 1;
    }
    printf("%d\n", L);
    return 0;
}