算法分析
二分答案的标准板题
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n, m;
cin >> n >> m;
vector<int> h(n);
rep(i, n) cin >> h[i];
int ac = 0, wa = 1001001001;
while (abs(ac-wa) > 1) {
int wj = (ac+wa)/2;
auto ok = [&]{
ll sum = 0;
rep(i, n) if (h[i] > wj) sum += h[i]-wj;
return sum >= m;
}();
(ok ? ac : wa) = wj;
}
cout << ac << '\n';
return 0;
}