逆序对的数量
这题一看就可以用暴力做,但是数据量要再大一点,就会TLE。
于是,我们就要调整一下思路。
解释:在分治后的每一层合并中顺便求出逆序对数量是这个题想法的由来,归并排序分治我们求的是从小到大的顺序,我们所求的逆序对恰好是逆序数量,与归并排序不谋而合。
这种方法当然可以,这种方法有一个名字:二路归并# 这种算法跟二分有点像,又跟归并排序的原理有点像,所以,我们可以用 归并排序的模版做,根据规则调整就行。
如 设有数列{6,202,100,301,38,8,1}
初始状态:6,202,100,301,38,8,1
第一次归并后:{6,202},{100,301},{8,38},{1},比较次数:3;
第二次归并后:{6,100,202,301},{1,8,38},比较次数:4;
第三次归并后:{1,6,8,38,100,202,301},比较次数:4;
总的比较次数为:3+4+4=11,;
逆序数为14;
于是,我们可以写出代码了:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100010;
int n;
int q[N];
LL merge_sort(int l,int r)
{
if (l>=r) return 0;
int mid=l+r>>1;
LL res=merge_sort(l,mid)+merge_sort(mid+1,r);
int k=0;
//归并的过程
int k=0,i=l,j=mid+1;
while(i<=mid&&j<=r)
if(q[i]<=q[j]) tmp[k++]=q[i++];
else
{
tmp[k++]=q[j++];
res+=mid-i+1;
}
//扫尾
while(i<=mid) tmp[k++]=q[i++];
while(j<=r) tmp[k++]=q[j++];
//物归原主
for(int i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
return res;
}
int main()
{
cin>>n;
for (int i=0;i<n;i++) cin>>q[i];
cout<<merge_sort(0,n-1)<<endl;
return 0;
}
修改1:
int q[N],tmp[N];
修改2:
k多次声明;删除程序中 int k=0;