예산

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> budgets, int M) {
	int answer = 0;
	int high = -1;
	int low = 0;

	for (int i = 0; i < budgets.size(); i++)
		high = max(high, budgets[i]);

	while (low <= high) {
		int mid = (low + high) / 2;
		long long sum = 0;

		for (int i = 0; i < budgets.size(); i++) {
			if (budgets[i] > mid)
				sum += mid;
			else {
				sum += budgets[i];
			}
		}
		if (sum <= M) {
			answer = mid;
			low = mid+1;
		}
		else
			high = mid-1;
	}
	return answer;
}