이분탐색

#include <iostream>
#include <vector>
using namespace std;

int main() {

	int n, m;
	scanf("%d%d", &n, &m);

	long long sum = 0;

	vector <int> trees;

	int tmp;
	int max_h = -1;
	for (int i = 0; i < n; i++) {
		scanf("%d", &tmp);
		trees.push_back(tmp);
		if (max_h < tmp) max_h = tmp;
	}

	int high = max_h;
	int low = 0;
	int mid;
	int ans = 0;

	while (low + 1 < high) {
		mid = (high + low) / 2;
		sum = 0;
		for (int i = 0; i < n; i++) {
			if (trees[i] > mid)
				sum += trees[i] - mid;
		}

		if (sum >= m) {//sum이 너무 크다는거는.. mid가 작단거라서 탐색범위를 올려야함
			low = mid;
			if (ans < mid) ans = mid;
		}
		else high = mid;
	}
	printf("%d", ans);
}

이분탐색