예산

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
//0943 ~
// 10^9 = 10억
ll N,high,M;
vector<ll> v;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for(ll i=0;i<N;i++)
    {
        ll a;
        cin >> a;
        v.push_back(a);
        high=max(high,a);
    }
    cin >> M;
    ll left =1;
    ll right=high;
    ll ans=0;
    while(left<=right)
    {
        ll tot = 0;
        ll mid = (left+right)/2;
        for(auto a: v)
            if(a<mid) tot += a;
            else tot+= mid;
        /* 예산이 크면 절대 답이 될 수 없으므로 상한액을 줄여야함 */
        if(tot > M)
            right = mid - 1;
        else{
            ans = max(ans,mid);
            left = mid + 1;
        }
    }
    cout << ans;
    return 0;
}