[백준 2512] 예산

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

2512번: 예산

요구사항

1. 상한선 금액 구하기

 

풀이

1. 그대로 금액 배정 가능한지 확인

2. 안된다면 이분 탐색으로 상한액 책정

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
ll n, m;
ll map[10001];
ll sum;
ll ans = 0;
void solve() {
	ll low = 0;
	ll high = m;
	ll maxv = 0;
	ll nowtemp = 0;
	ll maxv1 = 0;
	for (int i = 0; i < n; i++) {
		nowtemp += map[i];
		maxv1 = max(maxv1, map[i]);
	}
	if (nowtemp <= m) {
		ans = maxv1;
		return;
	}
	while (low <= high) 
	{
		ll mid = (low + high) / 2;
		ll temp = 0;
		for (int i = 0; i < n; i++) {
			if (map[i] < mid){
				temp += map[i];
			}
			else {
				temp += mid;
			}
		}
		if (temp <= m) {
			ans = max(mid, ans);
		}
		if (temp >= m) {
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
}
int main() 
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> map[i];
	}
	cin >> m;
	solve();
	cout << ans << endl;
}