1 2 3 4 5 ↓ 2 5 1 4 3 \/ \/ \/ \/ 3 +4 +3 +1 = 11
並び替えた後の数列を、偶数番目と奇数番目にわけると、どちらかが中央値以上、どちらかが中央値以下に分けられる。
5 4 2 1 3
そこで、中央値で区切ってみると、端以外は「中央値との差分」×2、端は×1の合計となる。
5 4 2/ \2 1/ \1 -------------------3 /1 2\ /2 0\ 2 1 3
なので、1回しかカウントされない端に、中央値に近い2数を持ってくれば、それが最大となる。
$N$ が奇数の時は中央値に近い2数が2通り考えられるので、両方試す。
import sys
n = int(input())
aaa = [int(line) for line in sys.stdin.readlines()]
aaa.sort()
if n % 2 == 0:
m1, m2 = aaa[n // 2 - 1], aaa[n // 2]
mid = sum(abs(a - m1) for a in aaa)
ans = mid * 2 - (m2 - m1)
else:
m1, m2, m3 = aaa[n // 2 - 1], aaa[n // 2], aaa[n // 2 + 1]
mid = sum(abs(a - m2) for a in aaa)
ans = mid * 2 - min(m2 - m1, m3 - m2)
print(ans)
N=6
1 2 3 4 5 6
S1 o o o
S2 o o o
S3 o o o
S4 o o o
'o'はどれも2つ）まず、適当に大きな $N$ を考えて、$S_1$ をたとえば$\{1,2,3,4\}$の4つの要素からなるとする。すると、
よって、作る集合の数は5つでないといけないと分かる。
次に各集合の要素数を考える。たとえば上で「1を含むもう1つの集合」の要素数が5だったりすると、今度はその集合をメインに同じことを考えると、作る集合の数は6にならないといけなくなり、矛盾する。よって、集合の要素数は全て同じ。
一般化すると、
この形で表せない $N$ は不可能とわかる。
そこまでわかれば、割り振り方を実験してみる。$N$ ではなく $k$ を基準にして考えてみる。
k=4 1 2 3 4 5 6 7 8 9 10 S1 o o o o S2 o あと3つ S3 o あと3つ S4 o あと3つ S5 o あと3つ
これを見ると、$S_2～S_5$ で残された各あと3つの決め方は、$k=3$ の時と全く同じ方法が使えることに気付く。
1 2 3 4 5 6 7 ... S1 o o o o S2 o o o o S3 o o あと2つ S4 o o あと2つ S5 o o あと2つ
さらに $k=3$ の決め方は $k=2$ に分解できる。
1 2 3 4 5 6 7 8 9 10 S1 o o o o S2 o o o o S3 o o o o S4 o o o o S5 o o o o
よって、$N=k(k+1)/2$ で表せさえすれば、再帰的に割り振り方が存在すると言える。
具体的に各集合の数字を書き出してみると、
N = 15 1 2 3 4 5 | o-----------o 1 6 7 8 9 | o o--------o 2 6 10 11 12 | | o o-----o 3 7 10 13 14 | | | o o--o 4 8 11 13 15 | | | | o o 5 9 12 14 15 | o o o o o
なので $(k+1) \times k$ の配列に順に埋めていけばいい。
def check(n):
i = 1
while n > 0:
n -= i
if n == 0:
return i
i += 1
return False
def solve(n):
k = check(n)
if k == False:
print('No')
return
buf = [[k] + [0] * k for _ in range(k + 1)]
t = k
u = 1
for i in range(k):
buf[i][i + 1:i + t + 1] = list(range(u, u + t))
for j in range(t):
buf[i + j + 1][i + 1] = u + j
u += t
t -= 1
print('Yes')
print(k + 1)
print('\n'.join(' '.join(map(str, b)) for b in buf))
n = int(input())
solve(n)