题目
n个小朋友站成一排。
现在要把他们按身高从低到高的顺序排列,但是每次只能交换位置相邻的两个小朋友。
每个小朋友都有一个不高兴的程度。开始的时候,所有小朋友的不高兴程度都是 0。
如果某个小朋友第一次被要求交换,则他的不高兴程度增加 1
,如果第二次要求他交换,则他的不高兴程度增加 2(即不高兴程度为 3),依次类推。当要求某个小朋友第 k
次交换时,他的不高兴程度增加 k。
请问,要让所有小朋友按从低到高排队,他们的不高兴程度之和最小是多少。
如果有两个小朋友身高一样,则他们谁站在谁前面是没有关系的。
输入
输入的第一行包含一个整数 n,表示小朋友的个数。
第二行包含 n 个整数 H1,H2,…,Hn,分别表示每个小朋友的身高。
输出格式
输出一行,包含一个整数,表示小朋友的不高兴程度和的最小值。
样例
输入样例:
3
3 2 1
输出样例:
9
代码
#include<iostream>
using namespace std;
typedef pair<int,int> PII;
const int N = 100010;
int n;
PII q[N],tmp[N];
int sum[N];
void merge_sort(int l,int r){
if(l>=r) return ;
int mid = l+r>>1;
merge_sort(l,mid);
merge_sort(mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid && j<=r){
if(q[i]<=q[j]){
sum[q[i].second] += j-mid-1;
tmp[k++] = q[i++];
}else {
sum[q[j].second] += mid-i+1;
tmp[k++] = q[j++];
}
}
while(i<=mid){
sum[q[i].second] += j-mid-1;
tmp[k++] = q[i++];
}
while(j<=r) tmp[k++] = q[j++];
for(i=l,j=0;i<=r;i++,j++) q[i] = tmp[j];
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&q[i].first),q[i].second = i;
merge_sort(0,n-1);
long long res = 0;
for(int i=0;i<n;i++) res += (long long)sum[i]*(sum[i]+1)/2;
printf("%lld",res);
}