二分答案-P1873 砍树

P1873 砍树
题目来源-洛谷题库

参考代码

#include <bits/stdc++.h>
using namespace std;
const int M = 1e6+5;
int n, m, a[M], l = 0, r = -1, ans = -1;// 判断是否满足条件 
bool check(int x) {long long sum = 0;for(int i=1; i<=n; i++) {  sum += max(0, a[i]-x); //高度不能为负数 }return sum >= m;   // 砍出的总和是否大于m
} int main() {cin >> n >> m;for(int i=1; i<=n; i++) {cin >> a[i];r = max(r, a[i]);  // 确定右边界，为最高的树的高度}while(l <= r) {  // 二分答案int mid = l + (r-l)/2; if(check(mid)) { //缩小区间ans = mid;  l = mid + 1; } else {r = mid-1; }}cout << ans;
}