分治法解决逆序对

用分治法来解决，这样能把n2变成nlogn

#include<iostream>

#include<stdio.h>
#include<vector>
using namespace std;
vector<int>A;
int hanshu(vector<int>&A)
{
int n=A.size();//当前数组长度
if(n<=1) //当只剩一个的时候不需要比较
return 0;
vector<int>B(A.begin(),A.begin()+n/2);//平均分开
vector<int>C(A.begin()+n/2,A.end());
int cnt=0;
    cnt+=hanshu(B);//纯左边
cnt+=hanshu(C);//纯右边
   
//接下来处理横跨两边的。我们本质上是枚举的c！！！
int ai=0;
int bi=0;
int ci=0;
while(ai<n)//遍历每一个数
{
         if(bi<B.size()&&(ci==C.size()||B[bi]<=C[ci]))//如果对于当前bi，当前的值比ci要小，说明他不会和右边的组成逆序对
{               //ci==C.size(),我们本质是枚举的C，拿b的和C比，但是如果c已经枚举完了，那么b的无脑放即可
             A[ai++]=B[bi++];
}
else//如果bi的大于ci，当前bi能组成，那么比bi还要大的属于B数组的也可以组成。
{
cnt+=n/2-bi;
A[ai++]=C[ci++];//ci++即可
}
}
return cnt;
    


}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int uu;
cin>>uu;
A.push_back(uu);
}
cout<<hanshu(A)<<endl;
}

最后

以上就是危机小蘑菇为你收集整理的分治法解决逆序对的全部内容，希望文章能够帮你解决分治法解决逆序对所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。