BZOJ1816（二分）

反思

• 由于受我第一次遇到的构造最多三角形的题的影响，这种几个分成一组最多多少组的题我老是往贪心上想。
• 事实上一般贪心也能贪，但这道题，还有突然想起的前些天做的cf140C，都是用二分可以更简单地解决，原因之一是分配最多的组数一般具有单调性。
• 想到二分就是水题了。

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 55;
int n, m, a[maxn];

bool ok(int mid) {
    int sum = min(mid, m);
    for (int i = 1; i <= n; i++) {
        if (a[i] < mid) {
            sum -= mid - a[i];
            if (sum < 0)    return 0;
        }
    }
    return 1;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int l = 0, r = 1e9, ans;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (ok(mid))    ans = mid, l = mid + 1;
        else    r = mid - 1;
    }
    return !printf("%d\n", ans);
}

BZOJ1816（二分）

原文：https://www.cnblogs.com/AlphaWA/p/10988366.html