逆序对定义:对于给定的一段正整数序列,逆序对就是序列中 $a_i>a_j$ 且 $i<j$ 的有序对。
P1908 逆序对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<bits/stdc++.h> #define int long long using namespace std; const int N=2e6+10; int n,m,a[N],c[N],res,num; void msort(int l,int r) //归并排序开始 { if(l==r) return; //递归终止 int mid=l+r>>1,i=l,j=mid+1,num=l; msort(l,mid),msort(mid+1,r); //确保两边均有序 while(i<=mid&&j<=r){ if(a[j]>=a[i]) c[num++]=a[i++]; else c[num++]=a[j++],res+=mid-i+1; //由于左半部分一定是有序的,所以从i到mid的数都比a[j]大,均为逆序 } while(i<=mid) c[num++]=a[i++]; while(j<=r) c[num++]=a[j++]; for(int i=l;i<=r;i++) a[i]=c[i]; } signed main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; msort(1,n); //归并排序 cout<<res; }
P1774 最接近神的人 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
由于题目要求每次只能交换相邻的 $2$ 个数,最终形成一个不降的序列,所以我们只能把所有逆序的数全部对换即可完成,也就是求出序列的逆序对
#include<bits/stdc++.h> #define int long long using namespace std; const int N=2e6+10; int n,m,a[N],c[N],res,num; void msort(int l,int r) //归并排序开始 { if(l==r) return; //递归终止 int mid=l+r>>1,i=l,j=mid+1,num=l; msort(l,mid),msort(mid+1,r); //确保两边均有序 while(i<=mid&&j<=r){ if(a[j]>=a[i]) c[num++]=a[i++]; else c[num++]=a[j++],res+=mid-i+1; //由于左半部分一定是有序的,所以从i到mid的数都比a[j]大,均为逆序 } while(i<=mid) c[num++]=a[i++]; while(j<=r) c[num++]=a[j++]; for(int i=l;i<=r;i++) a[i]=c[i]; } signed main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; msort(1,n); //归并排序 cout<<res; }
标签:归并,int,mid,msort,++,num,排序,逆序 From: https://www.cnblogs.com/o-Sakurajimamai-o/p/17984937