题目传送门
题目思路
比较简单,先找到最高的高度,然后二分查就行了,条件是在这个mid值(mid就是最后的结果)下的木材够不够就行了,不够就下移,够就上移,直到最后上下界相等输出就行了。
注意题目的数据范围,求和使用longlong。copilot真的强
AC代码
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
long long m;
int maxh = 0;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; i++)
{
cin >> a[i];
if (a[i] > maxh)
maxh = a[i];
}
int l = 0, r = maxh;
while (l < r && l != r)
{
int mid = (l + r) / 2;
long long sum = 0;
for (int i = 0; i < n; i++)
{
if (a[i] > mid)
sum += a[i] - mid;
}
if (sum >= m)
l = mid + 1;
else
r = mid;
}
cout << l-1 << endl;
return 0;
}