[2512] 예산

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

2512번: 예산

모든 예산을 배정할 수 있는 경우에만 예외처리해주면, 그 외에는 간단하다.

입력된 예산 요청액에 대해서, min(a[i], mid)를 누적해주고, 누적된 값이 총예산액을 초과하는지를 판별한다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

int n, m, ans;

vector<int> a;

bool f(int mid) {

    int i, cur = 0;

    for (i = 0; i < n; i++) cur += min(a[i], mid);

    return cur <= m;

}

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n;

    a.resize(n);

    int i;

    for (i = 0; i < n; i++) cin >> a[i];

    cin >> m;

    if (accumulate(a.begin(), a.end(), 0) <= m) {

        cout << *max_element(a.begin(), a.end());

        return 0;

    }

    int s = 0, e = (int)(1e9 + 0.5);

    while (s <= e) {

        int mid = s + e >> 1;

        bool ret = f(mid);

        if (ret == true) {

            ans = max(mid, ans);

            s = mid + 1;

        } else

            e = mid - 1;

    }

    cout << ans;

    return 0;

}

---