🎈 原创

洛谷 P1873 砍树

题目描述

伐木工人米尔科需要砍倒M米长的木材。这是一个对米尔科来说很容易的工作，因为他有一个漂亮的新伐木机，可以像野火一样砍倒森林。不过，米尔科只被允许砍倒单行树木。

米尔科的伐木机工作过程如下：米尔科设置一个高度参数H（米），伐木机升起一个巨大的锯片到高度H，并锯掉所有的树比H高的部分（当然，树木不高于H米的部分保持不变）。米尔科就行到树木被锯下的部分。

例如，如果一行树的高度分别为20，15，10和17，米尔科把锯片升到15米的高度，切割后树木剩下的高度将是15，15，10和15，而米尔科将从第1棵树得到5米，从第4棵树得到2米，共得到7米木材。

米尔科非常关注生态保护，所以他不会砍掉过多的木材。这正是他为什么尽可能高地设定伐木机锯片的原因。帮助米尔科找到伐木机锯片的最大的整数高度H，使得他能得到木材至少为M米。换句话说，如果再升高1米，则他将得不到M米木材。

输入格式

第1行：2个整数N和M，N表示树木的数量（1<=N<=1000000）,M表示需要的木材总长度（1<=M<=2000000000）

第2行：N个整数表示每棵树的高度，值均不超过1000000000。所有木材长度之和大于M，因此必有解。

输出格式

第1行：1个整数，表示砍树的最高高度。

输入输出样例

输入 #1

5 20
4 42 40 26 46

输出 #1

36

---

分析

如何判断这道题是需要二分的（因为是在二分的题集里）：

1.有单调性

提高伐木机的高度，最后得到的木头总量会减少，同样地，降低得到的木头会变多。而正因答案有单调性所以才可以使用二分。

2.数据范围大

1e6的N对于暴力枚举是不太友好的，穷举O(n * m)应该会超时，二分的话O(n * log m)应该是不会超时的。

---

代码

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

long long tree[1000010] = {0};
long long N, M, MAX = -1;

long long search(long long L, long long R);

int main(int argc, const char *argv[])
{
    cin >> N >> M;
    for(int i = 0; i < N; i++)
    {
        cin >> tree[i];
        if(tree[i] > MAX) MAX = tree[i];
    }
    cout << search(0, MAX) << endl;

    return 0;
}

long long search(long long L, long long R)
{
    while(L <= R)  //因为L和R的值是mid之后加减过的，加减过后是否满足还不确定，当最后L = R时还需要判断一次。
    {
        long long mid = (L + R) / 2;
        long long cnt = 0;
        for(int i = 0; i < N; i++)
            if(mid < tree[i])
                cnt += tree[i] - mid;
        if(cnt < M)
            R = mid - 1;  //这里一定要减一，不然会死循环，试想L = 3， R = 4，此时mid永远等于3
        else
            L = mid + 1;  // 同理
    }
    return R; //或者是 L - 1。在最后一次相等时判断后，如果少了，R就会减一，由于此时R的值是之前L的值，所以所以R一定满足条件。同样地，如果多了，L就会加一，但此时L的值是之前R取过的值，说明当前L的值必定不符合条件，所以只能取L - 1，也就是R。
}

感觉还是说不太清楚，表达能力实在有限，不知道怎么把想法表达出来，可能这就是我语文一直学不好的原因吧😅。

其他

还有一道一样的题，洛谷P2440

思路和所有的注意点都一摸一样，这里就直接给代码了。

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

long long N, K, MAX = -1;
long long wood[100010];

int main(int argc, const char * argv[])
{
    cin >> N >> K;
    for(int i = 0; i < N; i++)
    {
        cin >> wood[i];
        if(wood[i] > MAX)
            MAX = wood[i];
    }
    long long L = 1, R = MAX;
    while(L <= R)
    {
        long long mid = (L + R) / 2;
        long long cnt = 0;
        for(int i = 0; i < N; i++)
            cnt += wood[i] / mid;
        if(cnt < K)
            R = mid - 1;
        else
            L = mid + 1;
    }
    cout << R << endl;


    return 0;
}