[백준] 2512번: 예산

https://www.acmicpc.net/problem/2512

2512번: 예산

가능한 한 최대한 이 중요한 문구이다.

1,2 번으로 풀이 방식이 안내되어있지만 간단히 말하면 min(상한액, 예산)은 필수로 배정해야하되, 최대한 많은 예산을 써야한다는 것이다.

상한액을 찾기 위해 binary search를 한다.

 

이 때 반드시 모든 지방에 최소한 상한액까지는 배정되어야한다는 점을 이용해 포인터 이동 기준은 배정 가능한 지방의 수로 삼는다.

#include <iostream>
#include <vector>
using namespace std;

pair<int,int> share(int limit, int total, vector<int> &budgets) {
	int cnt = 0;
	int total_price = 0;
	for(int i = 0;i < budgets.size();i++) {
		int price;
		if(budgets[i] > limit) {
			price = limit;
		}
		else {
			price = budgets[i];
		}

		// 등호 중요
		if(total >= total_price + price) {
			cnt++;
			total_price += price;
		}
		else {
			break;
		}
	}

	return make_pair(cnt, total_price);
}
int main() {
	int n, m, budget = 0, total_budget = 0, answer = 0;
	cin >> n;
	vector<int> budgets(n);
	for(int i = 0;i < n;i++) {
		cin >> budgets[i];
	}
	cin >> m;
	int left = 0;
	int right = m;
	while(left <= right) {
		int mid = (left + right) / 2;
		pair<int,int> result = share(mid, m, budgets);
		if(result.first < n) {
			right = mid - 1;
		}
		else {
			budget = mid;
			total_budget = result.second;
			left = mid + 1;
		}

	}
	for(int i = 0; i < budgets.size();i++) {
		int price = min(budget, budgets[i]);
		answer = max(answer, price);
	}

	cout << answer << '\n';
}