二分大杂烩

这里声明整数二分模板，一个即可通关所有整数二分问题，而浮点数二分可以忽略，不会有边界问题。

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

当求最小值时，check 函数按照满足要求来， $ans= l$

当求最大值时，check 函数按照刚好不满足要求来， $ans= l - 1$

一般遇到最大值最小，最小值最大，这样的题目一般可以用二分答案解决。

PS：一种在 CF 经常遇到的模板

需要两个模板，与我的简洁观念背道而驰

while(l + 1 < r) {//最大值
	int mid = l + r >> 1;
	if(check(mid)) l = mid;
	else r = mid;
}
ans = l
while (l + 1 < r) {//最小值
	int mid = l + r >> 1;
	if (check (mid)) r = mid;
	else l = mid;
}
ans = r

练习：

P1873 EKO 砍树

求最大值，则按照模板，check 函数按照不满足要求来，答案是 $l - 1$

P1024一元三次方程求解

double a, b, c, d;
double f(double x) {
    return a * x * x * x + b * x * x + c * x + d;
}
void solve() {
    cin >> a >> b >> c >> d;
    int cnt = 0;
    for (int i = -100;i <= 100;i++) {
        double x1 = i, x2 = i + 1;
        if (!f(x1)) {
            cout << fixed << setprecision(2) << x1 << " ";cnt++;
        }
        if (f(x1) * f(x2) < 0) {
            while (x2 - x1 >= 0.001) {
                double mid = (x1 + x2) / 2;
                if (f(mid) * f(x2) < 0) {
                    x1 = mid;
                } else {
                    x2 = mid;
                }
            }
            cout << fixed << setprecision(2) << x2 << " ";cnt++;
        }
        if (cnt == 3) {
            return;
        }
    }
}

P1678 烦恼的高考志愿

#define int long long
void solve() {
    int n, m;cin >> n >> m;vector<int>a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    sort(a.begin() + 1, a.end());
    int res = 0;
    while (m--) {
        int x;cin >> x;
        int pos = upper_bound(a.begin() + 1, a.end(), x) - a.begin();
        int ans = 0;
        if (pos > n) {
            ans = abs(a[n] - x);
        } else if (pos == 1) {
            ans = a[1] - x;
        } else {
            ans = min(a[pos] - x, abs(a[pos - 1] - x));
        }
        res += ans;
    }
    cout << res << '\n';
}

二分答案

P2440 木材加工

求最大值

#define int long long
void solve() {
    int n, k;cin >> n >> k;vector<int> a(n);
    int sum = 0;
    for (int i = 0;i < n;i++)cin >> a[i], sum += a[i];
    int l = 0, r = 1e9;
    while (l < r) {
        int mid = l + r >> 1;
        if (!mid) {
            cout << "0\n";return;
        }
        int cnt = 0;
        for (int i = 0;i < n;i++) {
            cnt += a[i] / mid;
        }
        if (cnt < k)r = mid;
        else l = mid + 1;
    }
    cout << l - 1 << '\n';
}

P2678 跳石头