【2018QBXT刷题游记】
Day4 TEST6
T3 game
【吐槽】这几天写了多少道game了！
【题目大意】长度为n的数列，第i次交换任意相邻元素需要付出i的代价。操作完的序列的丑陋度是B*逆序对个数，其中B是给定的常数。求丑陋度和操作所付出的代价之和最小值。
【冷静分析】继续在纸上写写画画，突然想起逆序对个数就是相邻交换恢复成有序序列的次数！所以只用统计出逆序对个数，判断一下什么时候i会大于b即可。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
const int MAXN=50005;
ll b,a[MAXN],tmp[MAXN],sum,ans;
int n;
void Merge(int l,int mid,int r){
int i=l;
int j=mid+1;
int k=l;
while(i<=mid&&j<=r){
if(a[i]>a[j]){
tmp[k++]=a[j++];
ans+=mid-i+1;
}
else tmp[k++]=a[i++];
}
while(i<=mid)tmp[k++]=a[i++];
while(j<=r) tmp[k++]=a[j++];
for(int i=l;i<=r;i++)
a[i]=tmp[i];
}
ll S(int x){return (ll)(1+x)*x/2;}
void Merge_sort(int l,int r){
if(l<r){
int mid=(l+r)>>1;
Merge_sort(l,mid);
Merge_sort(mid+1,r);
Merge(l,mid,r);
}
}
int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
scanf("%d%lld",&n,&b);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
ans=0;
Merge_sort(1,n);
sum=b*ans;
if(ans<=b){
sum=sum-ans*b+S(ans);
}
else{
sum=sum-b*b+S(b);
}
printf("%lld
",sum);
return 0;
}