Tenka1 Programmer Beginner Contest:C - Align
問題
解法
小さい数,大きい数,小さい数,... のように並べていくのが最適だと分かるので,隣り合う要素の差の合計の式を書くと,
(a_2 - a_1) + (a_2 - a_1) + ... + (a_(n-1) - a_n)
になる.ここで,両端の要素を除いた n - 2 項は2回ずつこの式に登場していて,両端の要素は1回ずつ登場していると分かる.よって,要素をソートして2回登場させるか1回登場させるかを決めて計算すればよい.N が奇数の場合は大きい数と小さい数の区切り方が2通りあるため,2通り計算して max を取る必要がある.
解答
一発 AC だったのでよかった.