P1873 [COCI 2011/2012

思路分析

典型的二分答案问题。求满足条件的最大高度，用开区间二分模板。

在输入时记录树的最大高度作为二分右边界
check(mid)：遍历所有树，计算以 mid 高度砍树能获得的木材总长
如果木材足够（>= M），说明高度还能抬高，左边界右移；否则右边界左移
最后输出左边界（包含了等于 M 的情况）

高度越低，砍到的木材越多；高度越高，木材越少。

代码实现

int l = -1, r = highest + 1;
while (l + 1 < r) {
    int mid = (l + r) / 2;
    if (check(arr, M, mid)) l = mid;
    else r = mid;
}
System.out.println(l);

static boolean check(int[] q, int m, int x) {
    long sum = 0;
    for (int h : q) sum += Math.max(0, h - x);
    return sum >= m;
}