天使と宿題 [技術室奥プログラミングコンテスト#4 Day1 K]

https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_k

解説

https://atcoder.jp/contests/tkppc4-1/submissions/6667931

まず重要なこととして、最終日は必ず見せてもらう必要があるということである。
最終日でA[N]ページ見せてもらうことにした場合は、最終日からA[N]ページ分見せてもらうことにする。
すると、残りは[1,N-A[N]]の部分を見せてもらうことになるが、
これは[N-A[N],N-1]から一番見せてもらえる日を選んで見せてもらえばいい。
これで貪欲していけば解ける。

int N, A[201010];
//---------------------------------------------------------------------------------------------------
int solve() {
    reverse(A, A + N);
    priority_queue<int> que;

    int ans = 0;
    int top = 0;
    while (top < N) {
        que.push(A[top]);

        int ma = que.top(); que.pop();

        ans++;
        top++;
        ma--;
        while (top < N and 0 < ma) {
            que.push(A[top]);
            top++;
            ma--;
        }
    }
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    cout << solve() << endl;
}