2512번_예산_BOJ

문제 링크

2512번 예산 : https://www.acmicpc.net/problem/2512

문제 설명 및 해결 아이디어

Parametric Search문제이다.

mid는 배정할 예산으로 설정한다.

문제의 요구대로, 각 지방의 예산요청액이 배정할 예산액보다 클 경우 예산액을 더해준다.

반대의 경우, 예산요청액을 더해준다.

그 합이 주어진 총 예산인 M보다 작거나 같을 경우, mid를 크게해준다.

반대의 경우, mid를 작게하여 M과 비슷해지도록 합을 작게 해준다.

코드

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long int
#define MAX_S 10001
ll n, m, res, exceHandling, excepSum;
ll rq[MAX_S];
 
void func() {
    ll left = 0, right = 1000000000LL;
    ll ret;
    while (left <= right) {
        ret = 0;
        ll mid = (left + right) / 2;
 
        for (int i = 0; i < n; ++i) {
            if (rq[i] > mid) {
                ret += mid;
            }
            else {
                ret += rq[i];
            }
        }
        if (ret <= m) {
            left = mid + 1;
            res = max(res, mid);
        }
        else if (ret > m) {
            right = mid - 1;
        }
    }
}
 
int main() {
    scanf("%lld", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &rq[i]);
        exceHandling = max(exceHandling, rq[i]);
        excepSum += rq[i];
    }
 
    scanf("%lld", &m);
    if (m >= excepSum) {
        printf("%lld\n", exceHandling);
        return 0;
    }
    res = -987654321LL;
    func();
    printf("%lld\n", res);
    return 0;
}