7K12 blog

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

ABC160 E - Red and Green Apples

f:id:tkr987:20200624051958p:plain

https://atcoder.jp/contests/abc160/submissions/11401406

  • 上位X個、上位Y個以外は無視できる。
  • 無色のリンゴを基準にして交換を考えることで O(N)

f:id:tkr987:20200624053329p:plain

まず、赤のリンゴX個と緑のリンゴY個以外は無視する。美味しさの総和を最大化するには最も小さい赤か緑のリンゴと最も大きい無色のリンゴを順番に交換(上書き)するのが最善。無色のリンゴがX+Y個を超えてる場合があるので、配列サイズ外を参照しないように注意して実装する。全体計算量は O(N \log N)