백준2512 예산

작성일 | In

문제 링크

  • http://icpc.me/2512

문제 출처

  • 2012 전국 본선 초등2, 중등1, 고등1

사용 알고리즘

  • Parametric Search

시간복잡도

  • O(n log m)

풀이

(이 문제)와 매우 유사한 문제입니다.

chk(int h) 함수를 상한액이 h일 때 국가 예산으로 충당할 수 있으면 true, 불가능하면 false를 반환하도록 만듭시다.
chk함수를 이용해 parametric search를 하시면 됩니다.

전체 코드

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
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;

int arr[10101];
int n, m;

bool chk(int h){
    int sum = 0;
    for(int i=0; i<n; i++){
        sum += arr[i]>h?h:arr[i];
    }
    //cout << h << "::" << sum << "\n";
    return (m >= sum);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i=0; i<n; i++) cin >> arr[i];
    cin >> m;

    int sum = 0;
    for(int i=0; i<n; i++) sum += arr[i];
    if(m >= sum){
        int ans = 0;
        for(int i=0; i<n; i++) ans = max(ans, arr[i]);
        cout << ans; return 0;
    }

    int l = 0, r = 1e9+7;
    int mid;
    while(l<=r){
        mid = (l+r)>>1;
        bool now = chk(mid);
        bool nxt = chk(mid+1);
        if(now && !nxt) break;
        if(!now) r = mid-1;
        else l = mid+1;
        //cout << "(" << l << ", " << r << ")\n";
    }
    cout << mid;
}