【Tenka1 Programmer Contest】C - Align
問題概要
の個の整数を好きな順番に並べたとき, 隣り合う要素の差の合計の最大値を求めよ.
制約
考察
とりあえず個の整数をソートする. 最小の数字と最大の数字は隣同士であってほしいお気持ちになったので, 一旦そこを並べる. 次は最小の方に2番目に大きい数字を, 最大の方に2番目に小さい数字を並べる. こんな感じで貪欲に差を大きくしていけば良さそう.
が奇数だったら最後一個余るけど, そこも貪欲に置けばいい.
ex.)
[1] →
[2] →
[3] →
よって, 21と求まった.
ACコード(Python3🐍)
n = int(input()) a = sorted([int(input()) for _ in range(n)]) res = a[-1] - a[0] minn,maxx = a[0],a[-1] for i in range(1,n//2): res += maxx - a[i] res += a[-1-i] - minn minn,maxx = a[i],a[-1-i] if n%2==1: res += max(abs(maxx-a[n//2]),abs(minn-a[n//2])) print(res)