BOJ)2512 예산

문제:icpc.me/2512

최소중의 최대를 구하는 전형적인 파라메트릭 서치 문제이다.

다만 주의해야 할 건 모든 인풋 a[i]의 합이 m보다 작을 경우 a[i]중에 최댓값을 출력해줘야 하는 예외 케이스가 있다.

#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
ll n, a[10000], m, lo, hi, ma, s;
int main() {
    scanf("%lld", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
        ma = max(a[i], ma);
        s += a[i];
    }
    scanf("%lld", &m);
    if (m >= s) {
        printf("%lld\n", ma);
        return 0;
    }
    lo = 0;
    hi = 21000000000;
    while (lo < hi) {
        ll mid = (lo + hi) >> 1;
        ll r = 0;
        for (int i = 0; i < n; i++) {
            if (mid >= a[i])
                r += a[i];
            else
                r += mid;
        }
        if (r <= m)
            lo = mid + 1;
        else
            hi = mid;
    }
    printf("%lld\n", lo - 1);
    return 0;
}