[BOJ] 예산

[BOJ] 예산

Problem URL : 예산

#include <iostream>

using namespace std;

long long n, m;
long long arr[10001];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	int low = 0, high = 0;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		if (high < arr[i]) {
			high = arr[i];
		}
	}
	cin >> m;
	
	long long ans = 0;
	while (low <= high) {
		int mid = (low + high) >> 1;
		long long sum = 0;
		for (int i = 0; i < n; i++) {
			if (arr[i] >= mid)
				sum += mid;
			else
				sum += arr[i];
		}
		if (sum <= m) {
			ans = mid;
			low = mid + 1;
		} else {
			high = mid - 1;
		}
	}
	cout << ans << endl;

	return 0;
}