# 문제 분류
이분 탐색
이분 탐색의 원리를 제대로 파악하지 못하면 풀기 힘든 문제. 1 3 5에서 4를 찾으려고 할 때 lo<=hi로 만들어진 이분 탐색의 경우에는 lo가 5를 가리킨 후에 이분 탐색이 종료되게 된다. 그러나 이 문제의 경우에서는 최소한 M개 만큼의 나무는 챙겨가야하므로, 똑같은 방식으로 이분 탐색을 돌린다면 M개 보다 적은 나무를 챙겨가게 된다. 따라서 만약 lo로 설정했을 때 잘리는 나무의 수가 같은 경우에는 그대로 챙겨가고, 그것이 아닌 경우에는 위에서 말한 이분 탐색의 특성이 적용된 것이므로 -1을 하여 원래 자리를 찾아가도록 한다.
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const ll MOD = 1e9 + 7;
const int stMAX = 1 << 18;
const int INF = 1e9;
int N, M, height;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
vi tree;
for (int i = 0; i < N; i++) {
cin >> height;
tree.emplace_back(height);
}
int l = 0, h = 1'000'000'000;
// binary search
while (l <= h) {
int m = l + h >> 1;
ll sum = 0;
for (int p : tree) {
if (p > m)
sum += p - m;
}
if (sum >= M) {
l = m + 1;
} else
h = m - 1;
}
cout << l - 1;
}