7K12 blog

猫でも分かるアルゴリズム解説

ABC141 D - Powerful Discount Tickets

f:id:tkr987:20200722040558p:plain

https://atcoder.jp/contests/abc141/submissions/15353189

  • priority_queueのtop、pop、pushを多用しリアルタイムに最大値を取得、更新する

f:id:tkr987:20200722041153p:plain

この類の問題は買う値段などを決め打ちして二分探索するような定跡もあるが、今回はokとなる値が不明となるため二分探索できない。したがって、貪欲だろうと予想する。なるべく大きい値を常に割引きしたほうが効率が良いので、priority_queueのtop、pop、pushを多用して1回あたり O(\log N)の処理で実現する。全体計算量は O((M+N) \log N)になる。