51nod 1019 逆序数 (分治)
程序员文章站
2022-05-08 18:06:24
...
在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如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 1
Output示例
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;
}