伐木

又到了伐木的季节，亚布力林业局引进了一台新的伐木设备：

这种设备能设定一个高度值（整数），并将所有树木大于此高度的部分锯下来。

例如，有四棵树的高度分别为20M、17M、15M、10M，把设备的高度设定为 15M，那么设备运行过后树的高度变为15M、15M、15M、10M（从第一棵树锯下 5M，从第二棵树锯下 2M，总共锯下 7M）。

现在林业局需要至少锯下长度为M米的木头，因为国家推行的环保政策，林业局不能锯下过多的木材。

需要将伐木设备的高度设定为多少才能使得获得的木材至少为 M 米？

换句话说，如果再将高度升高一米，将得不到 M 米的木材，如果将高度减少一米，将不能通过环保政策。

输入：

第一行两个整数 N 和 M，N 表示树木的数量，M 表示需要木材的长度。（1 ≤ N ≤ 1000000 , 1 ≤ M ≤ 2000000000）

第二行 N 个整数表示每棵树的高度（N ≤ 1000000000）。所有数据必有解。

输出：

一个整数，表示伐木的最高高度。

样例：

1
2
4 9
20 17 15 10
1
14

1.思路

image-20211011172453307

  1. 根据设定伐木设备的设定长度num[i]，利用fun()函数进行计算，能求出其能够获得的伐木量
  2. 根据当前能够获取的伐木量s与题目给定真实需要的伐木量m进行比较，从而调整左右指针
  3. 当左右指针逼近到一定范围时，表示最佳答案已经找到

2.代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
using namespace std;

long long n, m, num[1000005], rawr;

long long func(long long x) {
    long long t = 0;
    for (int i = 0; i < n; ++i) {
        if (num[i] > x) {
            t += num[i] - x;
        }
    }
    return t;
}

long long bs() {
    long long l = 0, r = rawr;
    while (l != r) {
        long long mid = (l + r + 1) / 2;
        long long s = func(mid);
        if (s >= m) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return l;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> num[i];
        rawr = max(rawr, num[i]);
    }
    cout << bs() << endl;
    return 0;
}