Description

 给你n个整数,请重新排列这些整数,使得式子的值最大,其中表示第i个整数。请输出S的最大值。

 

Input

第一行一个整数n(2 <= n <= 100000),表示数字的个数;

第二行为n个整数 (1 <= ai <= 1000000000)

Output

 输出一个整数,表示S的最大值。

 

Sample Input

2
2 1

Sample Output

1

HINT

 

Smax = (-1)^2 * (2 – 1) = 1

C++版本一

题解:

求出每个位置的系数,然后大的系数对应大的数,小的系数对应小的数,分别将系数和数列排序,然后一一对应就行了。

#include<bits/stdc++.h>
using namespace std;
#define LL long long 

const int N = 1e5 + 10;
int a[N], c[N];
int main() {
	int n;
	//freopen("data3.in", "r", stdin);
	//freopen("data3.out", "w", stdout);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 2; i <= n; i++) {
		if(i&1) c[i]--, c[i-1]++;
		else c[i]++, c[i-1]--;
	}
	sort(c+1, c+n+1);
	sort(a+1, a+n+1);
	LL ans = 0;
	for (int i = 1; i <= n; i++) ans += 1LL * c[i] * a[i];
	printf("%lld\n", ans);
	return 0;
} 

C++版本二

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
const int N=100000+100;
int t,n,m;
ll a[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    sort(a+1,a+n+1);
    ll sum=0;
    if(n%2==0){
        for(int i=1;i<=n/2;i++){
        sum-=2*a[i];
        }
        for(int i=n/2+1;i<=n;i++){
            sum+=2*a[i];
        }
        cout << sum+a[n/2]-a[n/2+1] << endl;
    }else{
        for(int i=1;i<=n/2+1;i++){
        sum-=2*a[i];
        }
        for(int i=n/2+2;i<=n;i++){
            sum+=2*a[i];
        }
        cout << sum+a[n/2]+a[n/2-1] << endl;
     }
    //cout << "Hello world!" << endl;
    return 0;
}