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;