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)