ABC472 B - Break a Stick

棒を折る

考え方

全ての場所で実際に折ってみればよい。
各折り方、左側と右側でそれぞれ長さを合計し、差の絶対値をとる。
それの最小値記録を答えればよい。

答えるだけなら以上で終わりなのだが、少し工夫したやり方がある。

まず、最初に全ての長さを右側の値として合計しておく。
その後、左にある部分から順に $1$ つずつ、右側合計から引いて左側合計に足していく。
こうすると、二重ループを避けることができる上に、処理も高速になる。

まあ、処理の高速化の方は、やったところでC問題以降でないと特に恩恵はないのだが……。

入力を受け取る。

n: 4
l: {5, 2, 3, 8}

最初は全て右側にあるものとして、左側合計を $0$、右側合計を $18$ とする。

左から $1$ つずつ移動すると、次のようになる。

左へ移す長さ	左側合計	右側合計	差の絶対値	最小値記録
$5$	$5$	$13$	$8$	$8$
$2$	$7$	$11$	$4$	$4$
$3$	$10$	$8$	$2$	$2$

よって、実際の $3$ 箇所の切れ込みの中では、最小値記録は $2$ となる。

この後、最後の $8$ も左へ移した状態まで同じように調べる。
このとき左側の合計は $18$、右側の合計は $0$ となる。
これは切れ込みで折った状態ではないが、差は $18$ なので最小値記録は更新されない。
したがって、答えは $2$ である。

特になし。

特になし。