本文主要是介绍信息学奥赛一本通1311：【例2.5】求逆序对，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1311：【例2.5】求逆序对
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 61497 通过数: 14704
【题目描述】
给定一个序列a1,a2,…,an�1,�2,…,��，如果存在i<j�<�并且ai>aj��>��，那么我们称之为逆序对，求逆序对的数目。
【输入】
第一行为n�,表示序列长度，接下来的n�行，第i+1�+1行表示序列中的第i�个数。
【输出】
所有逆序对总数。
【输入样例】
4
3
2
3
2
【输出样例】
3
【提示】
N≤10^5，Ai≤10^5。
用二分的归并排序来求出交换了几次（有几对逆序数）
#include<bits/stdc++.h>
using namespace std;
int n,a[100001],x1[100001];
long long cnt;
void msort(int x[],int l,int r)
{if(l>=r){return;}int l1=l,mid=(l+r)/2,r1=mid+1,x2=l;msort(x,l,mid);msort(x,mid+1,r);while(l1<=mid&&r1<=r){if(x[l1]<=x[r1]){x1[x2++]=x[l1++];}else{cnt+=mid-l1+1;x1[x2++]=x[r1++];}}while(l1<=mid){x1[x2++]=x[l1++];}while(r1<=r){x1[x2++]=x[r1++];}for(int i=l;i<=r;++i){x[i]=x1[i];}
}
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}msort(a,1,n);cout<<cnt;
}这篇关于信息学奥赛一本通1311：【例2.5】求逆序对的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
