54 lines
1.4 KiB
C++
54 lines
1.4 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
int n, m, ans;
|
||
int a[1000006];
|
||
|
||
//如果从k开始为高度进行锯树，那么是不是可以满足大于m的要求
|
||
bool work(int k) {
|
||
long long d = 0;
|
||
for (int i = 1; i <= n; i++)
|
||
if (a[i] > k) d += a[i] - k;
|
||
if (d >= m) return true;
|
||
else return false;
|
||
}
|
||
|
||
|
||
int main() {
|
||
//输入+输出重定向
|
||
freopen("../1309.txt", "r", stdin);
|
||
|
||
// n表示树木的数量，m表示需要的木材总长度
|
||
scanf("%d%d", &n, &m);
|
||
|
||
//l:树的最小值 r:树的最大值
|
||
int l = INT32_MAX, r = INT32_MIN;
|
||
for (int i = 1; i <= n; i++) {
|
||
scanf("%d", &a[i]);
|
||
//取得树的最大值
|
||
if (a[i] > r) r = a[i];
|
||
//取得树的最小值
|
||
if (a[i] < l) l = a[i];
|
||
}
|
||
//这次二分不是对数组的二分，而是对值的二分
|
||
while (l <= r) {
|
||
//二分点
|
||
int mid = (l + r) / 2;
|
||
//如果这个数可以满足大于m的要求
|
||
if (work(mid)) {
|
||
//记录当前值，但不一定是最优解，需要继续探测，缩小范围，直到l和r相遇，最终ans里保存的就是结果
|
||
ans = mid;
|
||
l = mid + 1;
|
||
} else { // 在大的这一半都不行，那么在小的一半中折半查找
|
||
r = mid - 1;
|
||
}
|
||
}
|
||
//输出结果
|
||
printf("%d", ans);
|
||
|
||
//关闭文件
|
||
fclose(stdin);
|
||
return 0;
|
||
}
|