[KOI]전국본선 2012 중등부 첫번째 문제

#include <stdio.h>
#include <algorithm>
using namespace std;

int n, money;
int city[10000];

bool valid(int mid) {
	int ret = 0;
	for (int i = 0; i < n; ++i) {
		ret += min(mid, city[i]);
	}
	return (ret <= money);
}

int main()
{
	int left = 0, right = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &city[i]);
		right = max(right, city[i]);
	}
	scanf("%d", &money);

	while (left != right) {
		int mid = (left + right + 1) / 2;
		if (valid(mid)) {
			left = mid;
		}
		else {
			right = mid - 1;
		}
	}

	printf("%d\n", left);

	return 0;
}