[6236] 용돈 관리

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

6236번: 용돈 관리

i일에 사용할 돈을 a[i]라고 입력받은 뒤, 초기에 가진 돈(cur)을 하나의 mid에 대해서

cur-a[i]가 음수인 경우에는 남은 돈을 통장에 넣고, mid만큼 통장에서 인출한다.

인출한 횟수(cnt)를 매번 기록해 두었다가, n번에 걸친 시뮬레이션이 끝나면

cnt<=m으로 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, cnt = 0;

    for (i = 0; i < n; i++) {

        if (mid - a[i] < 0) return false;

        if (cur - a[i] < 0) {

            cur = mid - a[i];

            cnt++;

        } else {

            cur -= a[i];

        }

    }

    return cnt <= m;

}

int main(void) {

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

    cin >> n >> m;

    int i;

    a.resize(n);

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

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

    ans = e;

    while (s <= e) {

        int mid = s + e >> 1;

        bool ret = f(mid);

        if (ret == true) {

            ans = min(mid, ans);

            e = mid - 1;

        } else

            s = mid + 1;

    }

    cout << ans;

    return 0;

}

---