Content

对于一个有 \(n\) 个数的数列\(\{x_1,x_2,x_3,...,x_n\}\)，它的价值 \(S=(x_1-x_2)+(x_2-x_3)+(x_3-x_4)+...+(x_{n-1}-x_n)\)。现在给定 \(n\) 个数，让你通过重新排序使得 \(S\) 最大。

数据范围：\(2\leqslant n\leqslant 100, |x_i|\leqslant 1000\)。

Solution

看上去这个 \(S\) 的表达式很复杂，但是，我们尝试化简一下：

\(S=x_1-x_2+x_2-x_3+x_3-x_4+...+x_{n-1}+x_n=x_1-x_n\)

这就说明，要使 \(S\) 最大，就要使第一个数和第 \(n\) 个数的差最大，也就是要使 \(x_1\) 最大， \(x_n\) 最小。也就是说， \(S\) 和 \(x_2,x_3,...,x_{n-1}\)无关！所以，我们就直接将其变成升序序列（主要是因为要使字典序最小），然后将第一个数和第 \(n\) 个数调换顺序，最终的序列就是我们要求的序列。

Code

#include <cstdio>
#include <algorithm>
using namespace std;

int n, a[100007];

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)	scanf("%d", &a[i]);
	sort(a + 1, a + n + 1);
	printf("%d ", a[n]);
	for(int i = 2; i < n; ++i)	printf("%d ", a[i]);
	printf("%d", a[1]);
	return 0;
}