Edit

【pythonでABC176を解説】C - Step

問題概要

問題ページ

C - Step
C - Step

問題ページへ移動する

問題文

\(N\) 人が \(1\) 列に並んでおり、前から \(i\) 番目の人の身長は \(A_i\) です。

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

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

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

制約

  • \(1 \leq N \leq 2\times 10^5\)
  • \(1 \leq A_i \leq 10^9\)
  • 入力は全て整数

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    mx = 0
    cnt = 0
    for i in range(n):
        if mx > a[i]:
            cnt += mx - a[i]
        mx = max(mx, a[i])
    print(cnt)


if __name__ == '__main__':
    solve()

-Edit
-