C - Align
Time limit : 2sec / Memory limit : 1024MB
Score : 400 points
Problem Statement
You are given N integers; the i-th of them is Ai. Find the maximum possible sum of the absolute differences between the adjacent elements after arranging these integers in a row in any order you like.
Constraints
- 2≤N≤105
- 1≤Ai≤109
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A1
:
AN
Output
Print the maximum possible sum of the absolute differences between the adjacent elements after arranging the given integers in a row in any order you like.
Sample Input 1
Copy
5
6
8
1
2
3
Sample Output 1
Copy
21
When the integers are arranged as 3,8,1,6,2, the sum of the absolute differences between the adjacent elements is |3−8|+|8−1|+|1−6|+|6−2|=21. This is the maximum possible sum.
Sample Input 2
Copy
6
3
1
4
1
5
9
Sample Output 2
Copy
25
Sample Input 3
Copy
3
5
5
1
Sample Output 3
Copy
8 题解：分奇数和偶数讨论。当为奇数时，一定是中间的两个数在左右边（两种情况）使得结果最大。偶数同理，更好枚举，只有一种情况。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>
#define ll long long
//#define local using namespace std; const int MOD = 1e9+;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int maxn = 1e5+; int main() {
#ifdef local
if(freopen("/Users/Andrew/Desktop/data.txt", "r", stdin) == NULL) printf("can't open this file!\n");
#endif int n;
int a[maxn];
ll mx = ;
ll sum[maxn];
scanf("%d", &n);
for (int i = ; i < n; ++i) {
scanf("%d", a+i);
}
sort(a, a+n);
for (int i = ; i < n; ++i) {
if (!i) sum[i] = a[i];
if (i) sum[i] = sum[i-]+a[i];
}
if (n&) {
if (n == ) {
mx = max(abs(*a[]-a[]-a[]), abs(*a[]-a[]-a[])); //当n=3时，特殊讨论一下
} else {
//如果是选择靠左边的两个数作为两个端点，那么他们一定是小于它们相邻的数的。
//同理，如果是选择靠左边的两个数作为两个端点，那么他们一定是大于它们相邻的数的。
//将需要算两次的数*2
mx = max(abs(*(sum[n-]-sum[n/])-*(sum[n/-])-(a[n/]+a[n/-])), abs(*(sum[n-]-sum[n/+])-*(sum[n/-])+(a[n/]+a[n/+])));
}
} else {
mx = abs(*(sum[n-]-sum[n/])-*(sum[n/-])+abs(a[n/]-a[n/-]));
}
printf("%lld\n", mx);
#ifdef local
fclose(stdin);
#endif
return ;
}