题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007 输入描述: 题目保证输入的数组中没有的相同的数字 数据范围： 对于%50的数据,size<=10^4 对于%75的数据,size<=10^5 对于%100的数据,size<=2*10^5
输入例子: 1,2,3,4,5,6,7,0
输出例子: 7
思路： 1)直接把数组映射到[1,2*10^5]的区间上，之后用树状数组就OK了 (PS：用的map，跑了600ms) 2)运用归并排序，在归并两个有序数组时进行统计(PS:LRJ大神的归并代码写的是真心短，这次就跑了190ms)
树状数组版本: #include<cstdio> #include<algorithm> #include<vector> #include<map> #include<cstring> using namespace std; const int maxn=200005; int c[maxn]; map<int,int>Map; int lowbit(int x){ return x&(-x); } int sum(int x){ int ret=0; while(x>0){ ret+=c[x]; x-=lowbit(x); } return ret; } void add(int x,int d){ while(x<maxn){ c[x]+=d; x+=lowbit(x); } } int InversePairs(vector<int> data) { if(data.size()==0) return 0; int res=0,len=data.size(); memset(c,0,sizeof(c)); vector<int>v(data); sort(v.begin(),v.end()); for(int i=0;i<v.size();i++){ Map[v[i]]=i+1; } for(int i=len-1;i>=0;i--){ add(Map[data[i]],1); res+=sum(Map[data[i]])-1; } return res; } int main(){ //freopen("in.txt","r",stdin); int n,x,ans=0; scanf("%d",&n); vector<int>v; for(int i=0;i<n;i++){ scanf("%d",&x); v.push_back(x); } ans=InversePairs(v); printf("%d\n",ans); return 0; } 归并排序版本: #include<cstdio> #include<algorithm> #incldue<vector> using namespace std; typedef long long ll; const int maxn=200005; int b[maxn]; ll ans=0; //区间用的左闭右开 void merge_sort(vector<int>&a,int l,int r){ if(l+1<r){ int mid=l+(r-l)/2; merge_sort(a,l,mid); merge_sort(a,mid,r); int p=l,q=mid,k=l; while(p<mid||q<r){ if(q>=r||(p<mid&&a[p]<a[q])){ b[k++]=a[p++]; } else{ b[k++]=a[q++]; ans+=mid-p;/*如果a[q]是最小值，因为a[p]及之后的数都会比a[q]大且在a[q]前面，所以都是逆序的*/ } } for(int i=l;i<r;i++){ a[i]=b[i]; } } } int main(){ //freopen("in.txt","r",stdin); int n,x; vector<int>data; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&x); data.push_back(x); } merge_sort(data,0,n); for(int i=0;i<n;i++){ printf("%d ",data[i]); } printf("\n"); printf("%lld\n",ans); return 0; }