티스토리 뷰

알고리즘 관련/BOJ

BOJ)2512 예산

JASON 자손9319 2017. 1. 25. 17:15

문제:icpc.me/2512


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)8012 한동이는 영업사원!  (2) 2017.01.25
BOJ)1761 정점들의 거리  (0) 2017.01.25
BOJ)2512 예산  (0) 2017.01.25
BOJ)1576 DNA점수  (0) 2017.01.25
BOJ)10265 MT  (0) 2017.01.24
BOJ)3977 축구 전술  (0) 2017.01.24
댓글
댓글쓰기 폼