51nod 1019 逆序数(分治)

xiaoxiao2021-02-28  9

 

在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

如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; }

 

 

 

 

转载请注明原文地址: https://www.6miu.com/read-1100218.html

最新回复(0)