問題 atcoder.jp 解法 問題を読んだ段階で、ソートを行うクエリをどう扱うか（普通にソートすると計算量くってTLEっぽい）がポイントと思われる。 そこで、次のように処理する。 キュー Q1と最小値を優先的に取り出す優先度付きキューQ2を用意して、クエリを…

問題 atcoder.jp 解法 問題を一見すると 「どの商品に何枚半額割引券を使えばよいか？」 という問題に見える。 だが半額割引券を1枚ずつ使っても結果は変わらない。 なので、 「一番値段が高い商品に1枚ずつ割引券を使う」 という貪欲法で解ける。 あとは、…

問題 atcoder.jp 解法 最小値を計算量低く取り出すデータ管理構造、優先度付きキュー（priority queue）を使うことがポイント。 Pythonではheapqとして提供されている。 全体に対する玉の数の上下はoffset変数を作って管理。 玉を追加する時は、offset値を引…