#2512 예산

# 문제

# 입력 및 출력

# 풀이

원래는 이분탐색 문제다

근데 나는 좀 다르게 풀었다

예산 요청을 하나씩 배당해주면서 최대 상한값을 찾도록 했다

#include <iostream>
#include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int>> pq;

int main() {
	int n, t, budget, sum = 0, maxv = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> t;
		pq.push(t);
		sum += t;
		maxv = maxv < t ? t : maxv;
	}
	cin >> budget;
	if (sum > budget) {
		maxv = 0;
		for (int i = n; i > 0; i--) {
			int ul = budget / i;
			maxv = ul > maxv ? ul : maxv;
			budget -= pq.top();
			pq.pop();
		}
	}
	cout << maxv;
}

정렬을 사용하기 귀찮아서 그냥 우선순위 큐를 하나 만들었음

어떤 예산 요청도 배정해주지 않았을때 ~ 마지막에서 두번째 요청까지 배정해주었을 때까지 반복해서 최대 상한값을 찾음

어떤 예산 요청도 배정해주지 않았을땐 예산을 n개로 나눠가지는 것이 상한값이 될 것이고

첫번째 예산 요청을 배정해주면 예산에서 첫번째 예산 요청 금액을 빼고 n-1개로 나눠가지는 것이 상한값이 될 것이다

이것을 마지막에서 두번째요청까지 배정해주었을때까지 보고 그 중에서 최대 상한값을 찾음

말로 설명하려니까 좀 이상한것같네ㅋㅋ

정석풀이는 이분 탐색이니까 이분탐색으로도 풀어봤다

#include <iostream>
#include <algorithm>
using namespace std;
int req[10000];
int n, m, result, sum;

int cal(int mid) {
	int sum = 0;
	for (int i = 0; i < n; i++) {
		if (mid < req[i]) sum += mid;
		else sum += req[i];
	}
	return sum;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> req[i];
		sum += req[i];
	}
	sort(req, req + n);
	cin >> m;
	if (sum > m) {
		int start = 1;
		int end = req[n - 1];
		int mid;
		while (start <= end) {
			mid = (start + end) / 2;
			int s = cal(mid);
			if (s <= m) {
				result = mid;
				start = mid + 1;
			}
			else end = mid - 1;
		}
		cout << result;
		return 0;
	}
	else cout << req[n - 1];
}

1부터 요청 금액중 가장 큰 금액까지를 범위로 두고 범위를 절반씩 줄여나가면서 상한값을 찾는 방식이다