日志
ZIXI需要木材,所以他决定亲自去伐木。
ZIXI 的伐木机工作流程如下:ZIXI 设置一个高度参数H(米),伐木机升起一个巨大的锯片到高度H,并锯掉所有树比H高的部分(当然,树木不高于H米的部分保持不变)。ZIXI 就得到树木被锯下的部分。
ZIXI 非常关注生态保护,所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 ZIXI 找到伐木机锯片的最大的整数高度H,使得他能得到的木材至少为M米。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
long long cut(const vector<int>& heights, int h){
long long wood = 0;
for(int height : heights){
if (height > h){
wood += height - h;
}
}
return wood;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<int> heights(n);
for (int i = 0; i < n; ++i) {
cin >> heights[i];
}
int maxheight = *max_element(heights.begin(), heights.end());
int low = 0, high = maxheight;
int ans = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
long long wood = cut(heights, mid);
if (wood >= m) {
ans = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
cout << ans <<'\n';
return 0;
}