けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 176 C - Step (灰色, 300 点)

Greedy の一番簡単なパターン

問題へのリンク

問題概要

 N 人が 1 列に並んでおり、前から  i 番目の人の身長は  A_{i} です。

それぞれの人の足元に、高さが 0 以上の踏み台を設置し、全ての人が次の条件を満たすようにしたいです。

条件:踏み台を込めて身長を比較したとき、自分より前に、自分より背の高い人が存在しない

この条件を満たす時の、踏み台の高さの合計の最小値を求めてください。

制約

  •  1 \le N \le 2 \times 10^{5}

考えたこと

先頭の人から順に考えていきましょう。まず、先頭の人については、特に踏み台を用意する必要はないです。もし先頭の人を高くしてしまうようなことをすると、後ろの人が無駄に厳しくなります。

次に 2 人目について考えてみましょう。もし 2 人目の身長が先頭の人以上であるならば、同様に踏み台を用意する必要はないです。一方、2 人目の身長が先頭の人よりも小さいならば、2 番目の人の高さが先頭の人と同じになるようにすればよいでしょう。いずれの場合においても、この時点で 2 人の高さの最大値は max(A[0], A[1]) となっています。

さらに 3 人目について考えてみましょう。もし 3 人目の身長が max(A[0], A[1]) 以上であるならば、何もする必要はないです。それより小さいならば、3 人目の身長が max(A[0], A[1]) となるようにします。いずれにしても、この時点で 3 人の高さの最大値は max(A[0], A[1], A[2]) となっています。

以下同様に、次のように考えれば良いです。


  • i = 0, 1, 2, ..., N-1 に対して
  • A[i] >= max(A[0], ..., A[i-1]) ならば、何もしない
  • A[i] < max(A[0], ..., A[i-1]) ならば、高さが A[i] - max(A[0], ..., A[i-1]) の踏み台を用意する

高速化

さて、各 i に対して、max(A[0], ..., A[i-1]) の値を毎回求める必要があります。これは毎回愚直に for 文を回していては間に合いません。そこで、次のようにします。

  • highest = max(A[0], A[1], ..., A[i-1]) であるとき
  • max(A[0], A[1], ..., A[i]) = max(highest, A[i]) となるので、毎回 highest = max(highest, A[i]) と更新していく

このように工夫することで、全体の計算量は  O(N) となります。

コード

#include <iostream>
using namespace std;

int main() {
    int N;
    cin >> N;
    long long res = 0;
    int highest = 0;
    for (int i = 0; i < N; ++i) {
        int A;
        cin >> A;
        if (A < highest) res += highest - A;
        highest = max(highest, A);
    }
    cout << res << endl;
}