人権なし

競プロで解いた問題や開発の進捗などの記録です

Tenka1 Programmer Beginner Contest:C - Align

問題

beta.atcoder.jp

解法

小さい数,大きい数,小さい数,... のように並べていくのが最適だと分かるので,隣り合う要素の差の合計の式を書くと,

(a_2 - a_1) + (a_2 - a_1) + ... + (a_(n-1) - a_n)

になる.ここで,両端の要素を除いた n - 2 項は2回ずつこの式に登場していて,両端の要素は1回ずつ登場していると分かる.よって,要素をソートして2回登場させるか1回登場させるかを決めて計算すればよい.N が奇数の場合は大きい数と小さい数の区切り方が2通りあるため,2通り計算して max を取る必要がある.

解答

beta.atcoder.jp

一発 AC だったのでよかった.

f:id:babcs2035:20181028144600p:plain