AtCoder Beginner Contest 135 C - City Savers【Python】

https://atcoder.jp/contests/abc135/tasks/abc135_c

AtCoder ProblemsのRecommendationで Difficulty: 330、Solve Probability: 53%でした。

今まであまり意識していませんでしたがアルゴ式で貪欲法の箇所を進めているためこういう問題が貪欲法なのかと思いながら解きました。

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans = 0

#1人前の勇者がモンスターを倒せる残りの数
pbi = 0

for i in range(N+1):
    ai = A[i]

    #biはi番目の勇者がモンスターを倒せる数
    if i == N:
        bi = 0
    else:
        bi = B[i]

    #1人前の勇者がモンスターを倒す数
    pbn = min(ai, pbi)
    ai -= pbn
    ans += pbn

    #勇者がモンスターを倒す数は街にいるモンスターの数が上限
    if ai >= bi:
        ans += bi
        bi = 0

    elif ai < bi:
        ans += ai
        bi -= ai
    
    pbi = bi

print(ans)