题解 洛谷 Luogu P1873 [COCI 2011/2012 #5] EKO / 砍树 二分答案 C/C++

题目传送门：

P1873 [COCI 2011/2012 #5] EKO / 砍树 - 洛谷 | 计算机科学教育新生态https://www.luogu.com.cn/problem/P1873思路：

很简单的二分答案

每次找区间中点 m，判断以 m 为高度砍下的木头是否够 h 即可

代码：

#define LL long long
#include <cstdio>
using namespace std;
const LL N = 1E6 + 10;
LL arr[N], n, h, l, r, m, ans;
LL mp(LL m)
{LL ret = 0;for (LL i = 0; i < n; i++) if (arr[i] > m) ret += arr[i] - m;return ret;
}
int main()
{scanf("%lld%lld", &n, &h);for (LL i = 0; i < n; i++){scanf("%lld", &arr[i]);if (arr[i] > r) r = arr[i];}while (l <= r){m = l + r >> 1;if (mp(m) >= h) ans = m, l = m + 1;else r = m - 1;}printf("%lld", ans);return 0;
}