P3853 [TJOI2007]路标设置

二段性：对于一个值x，如果能够通过添加不超过k个木棒使得最大距离小于等于x，那么所有大于x的值t都能够通过添加不超过k个木棍使得最大间距小于等于t.
复杂度：(O(nlog(L)))
还是类似的二分+贪心

#include<iostream>
using namespace std;

const int N = 100010;

int a[N];
int L, n, k;

int check(int x){ // 通过贪心找到能够使得最大距离小于等于x需要添加的最少的木棍数
    int cnt = 0, last = 0;
    for(int i = 0; i < n; i ++){
        if(a[i] - last > x){
            last += x;
            i --;
            cnt ++;
        }else last = a[i];
    }
    
    return cnt <= k;
}

int main(){
    cin >> L >> n >> k;
    
    for(int i = 0; i < n; i ++) cin >> a[i];
    
    int l = 1, r = 10000000;
    
    while(l < r){
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    
    cout << l << endl;
    
    return 0;
}