백준 2512번: 예산 - binary search cpp

https://www.acmicpc.net/problem/2512

2512번: 예산

 

#include <bits/stdc++.h>
using namespace std;

int n,m, sum, maxx;
vector<int> v;


bool decide(int c){
    long long cnt = 0;

    for(int i=0; i<n; i++){
        if(v[i] < c){
            cnt += v[i];
        }
        else cnt += c;
    }

    return cnt <= m;
}

void Input(){
    cin >> n;
    for(int i=0; i<n; i++){
        int t;
        cin >> t;
        v.push_back(t);
        sum+=t;
        maxx = max(maxx, t);
    }
    cin >> m;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    Input();


    if(sum<=m){
        cout << maxx <<'\n';
    }
    else {
        int lo = 1;
        int hi = 1e9;

        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (decide(mid)) {
                lo = mid + 1;
            } else hi = mid - 1;
        }

        cout << hi << '\n';
    }
    return 0;
}