codeforces A. Difference Row 解题报告

题目链接：http://codeforces.com/problemset/problem/347/A

题目意思：给出一个序列 a₁, a₂, ..., a_n，通过重排序列，假设变成 x₁, x₂, ..., x_n，使得 (x₁ - x₂) + (x₂ - x₃) + ... + (x_n - 1 - x_n) 的和最大。输出这个重排后的序列，不过这个序列在满足得到这个最大和的基础上字典序的排序是最小的。字典序排列即：

Sequence x₁, x₂, ... , x_p is lexicographically smaller than sequence y₁, y₂, ... , y_p if there exists an integer r (0 ≤ r < p) such that x₁ = y₁, x₂ = y₂, ... , x_r = y_r and x_r + 1 < y_r + 1.

以测试案例来说： 100 -50 0 50 -100 和 100 -50 50 0 -100 都可以得到最大和200，但是前者的排列是比后者小的，因为第三个数0比50要小！！！

一开始想得比较复杂，100！的排列？不可能的！然后发现这个式子的特殊性 (x₁ - x₂) + (x₂ - x₃) + ... + (x_n - 1 - x_n) 。最终是可以变成 x1 - xn的（中间的全部消去了），那问题就变成如何得到 x1 - xn 的结果是最大的，很自然的想到是拿序列中最大的数减去最小的数就可以满足。至于中间的排列，为了符合字典序最小，那么必须第一个数是整个序列中次小的数，接着依次排到整个序列第二大的数就可以了。为什么这样可以？因为最终中间的那一堆数肯定是被消去的。

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <stdio.h>
 4 #include <stdlib.h>
 5 using namespace std;
 6 
 7 const int maxn = 100 + 5;
 8 int a[maxn];
 9 
10 int main()
11 {
12     int i, n;
13     while (scanf("%d", &n) != EOF)
14     {
15         for (i = 0; i < n; i++)
16         {
17             scanf("%d", &a[i]);
18         }
19         sort(a, a+n);
20         printf("%d", a[n-1]);
21         for (i = 1; i < n-1; i++)
22             printf(" %d", a[i]);
23         printf(" %d\n", a[0]);
24     }
25     return 0;
26 }