二分板子

1.求最大值最小

while (l <= r){
    mid = (l + r) >> 1;
    if (check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
}

例题 洛谷p3853 路标设置

code#include<bits/stdc++.h>

using namespace std;
int l, n, k, a[100010], r, ll, mid, ans, cnt;
bool check(int mid){
    cnt = 0;
    for ( int i = 2; i <= n; i++){
        cnt += (a[i] - a[i-1] - 1) / mid;
    if (cnt > k) return false;
    }
    return true;
}
int main(){
    cin >> l >> n >> k;
    for ( int i = 1; i <= n; i++) cin >> a[i];
    r = l; ll = 1;
    while (ll <= r){
        mid = (ll + r) >> 1;
        if (check(mid)) ans = mid, r = mid - 1;
            else ll = mid + 1;
        }
    cout << ans ;
    return 0;
}

2.求最小值最大

while (l <= r){
    mid = (l + r) / 2;
    if (check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
}

注：防超出int 用 mid = l + ( r - l ) / 2;