题目链接

题目链接

题意

重排数组，使得相邻两数之差绝对值的最小值尽可能大。\(n\leq 10^5\)

题解

排序，为了方便表述考虑连边。如果某条边的跨度不足 \(\lfloor \dfrac{n}{2}\rfloor\)，我们可以通过调整覆盖它的某条边（变为交叉）来使答案不减。因此我们要连边使得每条边跨度都有 \(\lfloor \dfrac{n}{2}\rfloor\)。对于偶数这会连成一条链，对于奇数这会连成一个环，选一条边断掉即可。

from itertools import chain
input()
a=sorted([int(i) for i in input().split()])
n=len(a)
a=list(chain(*zip(a[n//2:],a[:n//2])))+([a[-1]]if n&1 else[])
q=n%2*min(range(n),key=lambda x:abs(a[x]-a[x-1]))
print(' '.join(str(i)for i in a[q:]+a[:q]))

花絮：搬题人只造了 \(n\) 为偶数的数据。