TCO17 Round 2C Easy CanidsSeesaw

問題

n匹の狼とn匹の狐がいる。 狼iの重さはwolf[i]、狐iの重さはfox[i]。 狼は入力で与えられた順で並んでいるが、狐の順番は自由に並べ替えられる。 i=1~nについて Σwolf[1..i] < Σfox[1..i] なら1ポイント獲得できる。 ちょうどkポイント獲得できるようなfoxの並べ方を求めよ。

解法

本番では辞書順最小の並びを求めるような方針で解いた。

が、バブルソート解の方が解法の正当性が証明しやすいし、実装も簡単でいい。 獲得できるポイントは辞書順最小のとき最小、辞書順最大のとき最大。 で、隣り合った要素をスワップしたときの獲得ポイントの変化は高々1なので、最小<=k<=最大ならば、バブルソートしていくと、どこかで必ずkポイント獲得する並びが得られる。

gist.github.com