BOJ 2512 예산

www.acmicpc.net/problem/2512

2512번: 예산

이분 탐색에 대해 공부하는 중이다. 간단한 문제지만 L, R 정하거나 ans값을 찾는 것이 한 번에 되지 않아서 연습해볼 만하다.

정부는 지방마다 각 예산을 할당해야 되는데 예산이 정해져 있어서 우선순위를 둬야 한다.

 

• 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
• 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산 요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 

간단히 말해서 이분 탐색 돌리다가 예산 값이 m값보다 커지면 그때의 L값을 가져가면 된다.

#include <cstdio>
#include <algorithm>
using namespace std;
using ll = long long;

int ar[10001];

int main() {
	int n, m;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", &ar[i]);
	scanf("%d", &m);
	ll L = 0, R = *max_element(ar, ar + n);
	while (L < R) {
		ll sum = 0, mid = (L + R + 1) / 2;
		for (int i = 0; i < n; i++) {
			if (ar[i] < mid) sum += ar[i];
			else sum += mid;
		}
		//printf("L= %lld mid = %lld R= %lld sum= %lld\n", L, mid, R, sum);
		if (sum > m) R = mid - 1;
		else L = mid;
	}
	printf("%lld", L);

	return 0;
}

L <=R을 하는지 반례는 무엇인지, 찾는 게 조금 힘들었다.