【ABC183 D】「Water Heater」を解く【Python3】

「AtCoder」解説一覧へ

毎分Wリットルのお湯を供給することができる給湯器が、条件通りすべての人にお湯を供給することができるかどうかを判定する問題です。

提出
n, w = map(int, input().split())
t = [list(map(int,input().split())) for _ in range(n)]

c = [0]*(2*10**5+1)

for i in t:
    si, ti, pi = i
    c[si] += pi
    c[ti] -= pi

for i in range(2*10**5):
    c[i+1] += c[i]

if max(c) <= w:
    print("Yes")
else:
    print("No")

N人の人がいて、i番目の人は時刻SiからTiまでの間、毎分Piリットル利用します。

時刻Siに利用者が増え、Tiに減ると考えて、累積和を用いてすべての時間のお湯の利用量を調べていきます。

すべての要素が0のリストcを作成し、時刻Siに「Pi」を足し、時刻Tiに「Pi」を引きます。

そのあとに、それまでの数値を累積して足していくループを作ります。

最後に、リスト内の最大値がw以下かどうかを判定し、答えを出力します。

入力例1の場合、リストcを途中まで出力すると、以下のようになります。

for i in range(2*10**5):
    c[i+1] += c[i]
print(c[:11])
# > [0, 5, 10, 11, 6, 6, 6, 6, 6, 6, 0]

この中で最大値は「11」であり、wより大きいため、答えは「No」となります。

【ABC183】解説記事リスト

「AtCoder」解説一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です