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;
}