[백준 16564번] C++ 히오스 프로게이머 (이분탐색)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int N;          //캐릭터수
	int K;
	int ans = 0;      //최대의 min(X_i)
	vector<int> levels;
	
	cin >> N >> K;

	int tmp;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		levels.push_back(tmp);
	}

	sort(levels.begin(), levels.end());
	int low = levels[0], high = levels[N - 1] + K;

	while (low <= high) {
		int mid = (low + high) / 2;  //mid는 T가 되고싶은 수
		long long need = 0;          //mid되려면 필요한 수 need에 저장해서 K와 비교
                                     //2000,000,000 넘는 수가 될 수 있으면 long long 쓰자. int로 안됨

		for (int i = 0; i < N; i++) {
			if (levels[i] < mid) need += (mid - levels[i]);
			else break;
		}

		if (need > K) high = mid - 1;
		else {    //(need<=K인 경우인데, 예제처럼 K를 다 쓰지 않는 경우도 있기 때문임)
			ans = max(ans, mid);
			low = mid + 1;
		}
	}

	cout << ans;
	return 0;
}