写在前面
贪心去构造这个排列比较显然,但感觉我的实现挺有趣的。
Description
题目传送。
Solution
Subtask1 显然是枚举全排列模拟整个操作,不在多说。
其他 Subtask 没细看。
发现那个 \(k\) 始终都是原始序列的值,修改的权值可以直接算进答案里。
所以第 \(i\) 次操作对整个答案的贡献就是 \((n-i) \times (-1)^{k+i+1} \times k\)。
贪心其实很好想。
为了让每个元素尽可能做出正贡献,我们要把正偶数负奇数放在奇数位,把正奇数负偶数放在偶数位,并且绝对值大的往前放。
显然我们可以把两类数拆开排序后模拟的放进去。需要特殊处理的是一类比另一类多的情况。
但这里有一个更简单的写法不用特殊处理。
我们把正偶数负奇数排在正奇数负偶数前面,对于正偶负奇内部按照绝对值从大到小排序,对于正奇负偶内部按照绝对值从小到大排序。
然后我们先填左边在填右边,这样交替填,刚好能满足正确的顺序。
并且我们通过这个顺序可以直接计算出答案。
Code
/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define int long long
#define orz cout<<"lkp AK IOI!"<<endl
using namespace std;
const int MAXN = 2e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;
int n, Ans = 0;
int a[MAXN];
int read(){
int s = 0, f = 0;
char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
return f ? -s : s;
}
bool cmp(int x, int y) {
if((x >= 0 && !(x & 1)) || (x < 0 && (x & 1))) {
if((y >= 0 && !(y & 1)) || (y < 0 && (y & 1))) {
return abs(x) > abs(y);
} else {
return true;
}
} else {
if((y >= 0 && !(y & 1)) || (y < 0 && (y & 1))) {
return false;
} else {
return abs(x) < abs(y);
}
}
}
signed main()
{
n = read();
for(int i = 1; i <= n; ++i) a[i] = read();
sort(a + 1, a + n + 1, cmp);
// for(int i = 1; i <= n; ++i) cout<<a[i]<<" "; puts("");
for(int i = 1; i <= n; ++i) Ans += a[i];
for(int i = 1, v = 1, l = 1, r = n; i <= n; ++i, v ^= 1) {
if(v) {
if((a[l] + i + 1) & 1) {
Ans -= (n - i) * a[l];
} else {
Ans += (n - i) * a[l];
}
l++;
} else {
if((a[r] + i + 1) & 1) {
Ans -= (n - i) * a[r];
} else {
Ans += (n - i) * a[r];
}
r--;
}
}
printf("%lld", Ans);
return 0;
}