- 考えたこと
- まず全部をAにして、それから「Bに変えた時の得」「Cに変えた時の得」をソートして、大きい方から取っていく
- これだと多分ダメなのだ。「Bにしても損だけどCにするとものすごく損だからBにするしかない」のパターンがあるから
- 公式解説
- 2種類の時には差でソートして大きい方から取っていく貪欲アルゴリズムが成立するので、問題を変形してからに帰着したい
- B-Aでソートした場合にAがBより左に来ることはない、その場合、交換しても悪化しないから
- なので境界線を引けば2種類の問題に帰着できる
- doing