在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如2 4 3 1中,2 1,4 3,4 1,3 1是逆序,逆序数是4。给出一个整数序列,求该序列的逆序数。
Input
第1行:N,N为序列的长度(n <= 50000) 第2 - N + 1行:序列中的元素(0 <= A[i] <= 10^9)Output
输出逆序数Input示例
4 2 4 3 1Output示例
4题目意思很明确。前面的数字大于后面的有多少对。
这道题可以用分治做,一般这种可以分区计算结果后处理的都可以用分治。简单说下分治
1:把范围分为尽量相等的两个区域,分别对两个区域计算结果
2:把分开的区域再分,得到两半区域结果进行处理。
那么对于本题目:
1:对范围一直递归,直到有一半只有一个元素(最小范围开始想),对面左边区域与右边区域的逆序对
比如: 左区域:1 右区域:3,2,答案为2对。(3,2)不算,因为同区域
2:计算完进行排序,方便上一层的计算,排序不影响上一层的运算,因为运算涉及两个区间,左区域排序后还是在右区域的左边
这个很难说,自己理解一下过程就觉得很有趣了,做个例子
3 1 4 2 5 分区域: 左边: 3 1 右边,4 2 5
左边进行运算,3>1 答案加一。加完排序: 于是左边: 1 3
右边进行运算,分为 左边:4 右边:2 5 因为4>2,答案加一。 排序:2 4 5
两边运算完成,返回上一层:1 3 2 4 5,分为两半运算(子区域已经运算完成):左:1 3 右边 2 4 5
3>2,答案加一,排序: 1 2 3 4 5。再把以这5个数为分区域的区域运算。
代码献上:
#include <iostream> #include <cstdio> #include <string.h> #include <fstream> #include <algorithm> using namespace std; int ans=0,a[50005],temp[50005],i,j,n,ok=0; void fenzhi(int l,int r) { int mid,t1,t2,t3=0,t4; if(r-l>1) { mid=l+(r-l)/2; t4=mid; fenzhi(l,t4); fenzhi(t4,r); t2=mid; t3=0; for(t1=l;t1<mid;t1++) { // cout<<"ok"; for(;t2<r;t2++) { if(a[t2]>=a[t1]) { temp[t3++]=a[t1]; ans+=t2-mid; break; } temp[t3++]=a[t2]; } // cout<<" ok"; if(t2==r) { ans+=(mid-t1)*(r-mid); for(t4=t1;t4<mid;t4++) temp[t3++]=a[t4]; break; } } for(t1=l;t1<r;t1++) a[t1]=temp[t1-l]; // sort(a+l,a+r); } } int main() { cin>>n; for(i=0;i<n;i++) cin>>a[i]; fenzhi(0,n); cout<<ans; return 0; }