题解 | #美#

考虑直接对输入的序列 $RR$ 排序，然后 $R_1,R_n,R_2,R_{n-1},\cdots R\_1,R\_n,R\_2,R\_\{n-1\},\backslash cdots$ 这样交替排列下去就好了。

考虑证明：（官方题解中好像没写明白哎）假如我们任意交换某两个 $R_i,R_{j}R\_i,R\_j$，那么按照这个序列逐个奇数位置递减偶数位置递增的方式，不难得到：

$R_{i}R\_i$ 两边的贡献和 $R_{j}R\_j$ 两边的贡献必然没有伸展到最开的位置。

不妨把这个信息扔到一个数轴上看一看，我们最初的排列方式，实际上就是在数轴上的两个最远点、再到次远点，这样来回穿梭：

如果改变某两个 $R_{i}R\_i$，$R_{j}R\_j$ 的位置，相当于把两个不那么远的点放到一起去算答案，一定劣于原始的情况。

最后注意到这是一个环，所以最后最近的某个位置还要与外面的某个点再算一次答案，注意处理一下即可。

#include<cstdio>
#include<algorithm>
#define int long long
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 1e5 + 5;
int a[N], b[N];
int ab(int x){
    return x < 0 ? -x : x;
}
signed main(){
    int n = init();
    for (int i = 1; i <= n; ++i)
        a[i] = init();
    std::stable_sort(a + 1, a + 1 + n);
    int l = 1, r = n, tp = -1;
    for (int i = 1; i <= n; ++i) {
        if (tp > 0) {
            b[i] = a[l++];
        }
        else {
            b[i] = a[r--];
        }
        tp *= -1;
    }
    int max = 0;
    for (int i = 1; i <= n; ++i)
        max += ab(b[i] - b[i + 1 > n ? 1 : i + 1]);
    print(max), putchar('\n');
}