归并排序求逆序对模板
程序员文章站
2022-05-10 15:05:48
...
//还是自己菜最后还是看了网上模板才写出来的
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e6+10;
LL num[N],a[N];
LL ans;
void Merge(int l,int mid,int r) //分治的治 合并是求逆序对的关键
{
int i=l,j=mid+1,k=l;
while(i<=mid&&j<=r)
{
if(num[i]>num[j]) //前半部分中比num[i]大的数都比num[j]大,将num[j]放在num[i]前面的话,逆序数要加上mid+1-i
{
a[k++]=num[j++];
ans+=mid-i+1; //统计逆序对
}
else //这里这情况不产生逆序对
a[k++]=num[i++];
}
while(i<=mid)
a[k++]=num[i++];
while(j<=r)
a[k++]=num[j++];
for(int e=l;e<=r;e++) //将这次操作完的num数组更新
num[e]=a[e];
}
void Merge_sort(int l,int r) //分治的分 在这里不断地把一个串细分然后回溯合并
{
if(l<r)
{
int mid=(l+r)/2;
Merge_sort(l,mid);
Merge_sort(mid+1,r);
Merge(l,mid,r);
}
}
int main()
{
ios::sync_with_stdio(false);
int n;
while(cin>>n&&n)
{
for(int i=0;i<n;i++)
cin>>num[i];
ans=0;
Merge_sort(0,n-1);
cout<<ans<<endl;
}
return 0;
}
上一篇: Nginx 负载均衡配置和策略
下一篇: 购物车解决方法