日志

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;

}

全部评论

相关推荐

评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务