ABC148 D - Brick Break
問題原文
問題要旨
整数列 が左から と並ぶようにするためには、いくつの数字を削除する必要があるか?
条件を満たせない場合には -1 を出力せよ。
解法
俗に言うスターリンソート。(?)
例えば、 とあった時に「1aと1bのどちらを残すべきか?」 と疑問に思うかもしれないが、1aを残すと決めた方が、1a~1b間の3つの x のいずれかが2であった時に得をする = 損することはない。
よって数列を左から見て行って、次に欲しい数が来た場合には、それを使うと確定して問題ない。
実装
N = int(input()) A = list(map(int, input().split())) next_break = 1 ans = 0 for a in A: if next_break == a: next_break += 1 else: ans += 1 if next_break == 1: print(-1) else: print(ans)
「next_break
が 1
のまま」 = 「1
が見つからなかった」なので、 -1
を出力する。
感想
ある操作をしても損をすることはない
という発想は、常に頭の引き出しに入れておきたいですね。