思路历程
一:为什么
要满足从低到高排队并且相邻交换
1:如果不考虑小朋友的满意度,直接用冒泡的思想(逆序则交换),假设逆序对有K个,那么K次必定能把序列变的有序(每一次交换使k减一)
2:考虑小朋友的满意度,对于每一个小朋友,交换次数最少是多少?显然左边比他大的要经过他,右边比他小的要经过他
所以每个小朋友的交换次数>=K1(左比他大)+K2(右比他小)
对于所有小朋友(K1+K2)+(K1+K2)+…=2K(这个K是逆序对数量,因为左边的数算了右边的逆序,右边也算了左边所以是两倍)
如果每一次操作都是最优操作的话,每一次操作一定会使得某一个(K1+K2)减2,(所以等号右边的2K也减2)
那么K次最优操作一定能把序列变的有序(同第二行),并且每一个小朋友的交换次数都=K1(左比他高)+K2(右比他矮)
二:怎么求
接下来就是归并求每个小朋友 左比他高的人个数+右比他矮的人的个数
因为要求每一个人的K1+K2的值(假设sum=k1+k2)因为每个小朋友的不满意度递增res+=sum*(sum+1)/2),所以不能直接求逆序对数量
而是要找到每一个小朋友的sum
1:假设小朋友身高各自都不同:直接用小朋友的身高当作数组下标来储存这个小朋友的不满意度
然后枚举每一个小朋友的身高就可以得到sum(小朋友身高不是很大所以可以用数组代替map)
2:现在小朋友的身高可能会相同:每一个小朋友现在能体现不同的地方只有他们各自的下标了
所以此时用一个数组(我这里数组名是cun)存下每一个小朋友的编号(下标),然后merge_sort看似是在给cun排序实际上是在按照q的值排序(也就是下面的q[cun[i]]<=q[cun[j]])
用下标cun数组排序的好处就是每一个小朋友都是两两不同的,所以在归并中求到的k1和k2就可以直接赋值给此时的编号cun[i],cun[j]
在归并的时候
如果从左边弹出一个数,那这个数对应的右边比他小的数就是右边已经弹出的数的个数是j-(mid+1)
如果从右边弹出一个数,那这个数对应的左边比他大的数就是左边还未弹出的数的个数是mid-i+1
最后遍历一下cun数组就可以了
(cun数组的含义可以参考一下利用cun排序的sort()比较函数bool cmp(int a,int b){return q[a]<q[b];}
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int N=1e6+10;
int n,m;
int q[N],c[N];
int mp[N],cun[N];
void merge(int l,int r)
{
if(l>=r)return ;
int mid=l+r>>1;
merge(l,mid),merge(mid+1,r);
int i=l,j=mid+1,k=0,cnt=0;
while(i<=mid&&j<=r)
{
if(q[cun[i]]<=q[cun[j]])mp[cun[i]]+=j-(mid+1),c[k++]=cun[i++];
else mp[cun[j]]+=mid-i+1,c[k++]=cun[j++],cnt++;
}
while(i<=mid)mp[cun[i]]+=j-(mid+1),c[k++]=cun[i++];
while(j<=r)c[k++]=cun[j++];
for(int i=l,j=0;i<=r;i++,j++)cun[i]=c[j];
return;
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>q[i],cun[i]=i;
/*
这两句话表达一下cun的意义,cmp在解析最后一行
sort(cun,cun+n,cmp);
for(int i=0;i<n;i++)cout<<q[cun[i]]<<" ";
*/
merge(1,n);
int res=0;
for(int i=1;i<=n;i++)
res+=mp[cun[i]]*(mp[cun[i]]+1)/2;
cout<<res<<endl;
}
signed main()
{
IOS;
int T=1;
//cin>>T;
while(T--)
solve();
return 0;
}