No.545 ママの大事な二人の子供
タグ : / 解いたユーザー数 146
作問者 :
horiesiniti
/ テスター :
37zigen
問題文
ママには二人の大事な子供AとBがいます。 ママは二人を平等に愛しており、二人を分け隔てなく育てています。 ママは今ｎ個の品物を持っており、ｎ個全てを２人に分配しようとしています。 しかし二人は、品物をもらったとき、品物に対する満足度が違います。 Aがあんパンをもらえば、Aの満足度は15でBがもらえばBの満足度は３０だという具合です。 ママは二人とも大好きなので、Aの満足度合計とBの満足度合計の差異が最小になるように品物を分配することにしました。 データから差異の最小値（つまり差の絶対値）を求めるプログラムを書いてください。 データは以下の通り。
品物の数ｎ。
つづくｎ行に品物に対する二人の満足度AiとBiが与えられます。
A1ならAが品物１をもらったときの満足度。B1なら品物1をBがもらったときの満足度。
AiならAが品物iをもらったときの、BiならBが品物iをもらったときの満足度という具合です。
入力
$n$
$A_1$ $B_1$
$A_2$ $B_2$
$\dots$
$A_{n}$ $B_{n}$
$1 \leq n \leq 32$
$0 \leq Ai \leq5000000000$
$0 \leq Bi \leq5000000000$
Ai,品物iをAがもらったときのAの満足度、Biは品物iをBがもらったときのBの満足度です。
２人とも品物をもらったときの満足度を単純合計し、満足度の差異が最小になるように分配されたときの満足度合計差異を計算してください。
出力
2人の満足度差異絶対値の最小値を出力してください。
サンプル
サンプル1
入力
1 10 15
出力
10
品物が一個しかなくBに分けるよりはAに分けるほうが満足度の差異が少ない。 母は満足度の最高値を目指しているのではなく、分配に置ける差異を最少化したいのだ。 全部の品物をAとBに配るという条件なので配らないという選択肢はない。 全部の品物がAかBどちらかだけに配られるケースもあり得る。
サンプル2
入力
3 25 14 25 23 32 10
出力
1
品物１と３をBに品物２をAに分配すれば差分が最小化される。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。