求逆序对

ゞ浴缸里的玫瑰 2023-02-11 03:21 16阅读 0赞

题型: 编程题 语言: 不限定

## Description ##

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。  
一个排列中逆序的总数就称为这个排列的逆序数。逆序数是课程线性代数的一个知识点。  
现在给定一个排列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称ai和aj为一个逆序，请求出排列的逆序数。

## 输入格式 ##

第一行为n,表示排列长度。(1=<n<=100000)  
第二行有n个整数，依次为排列中的a1,a2,…,an。所有整数均在int范围内。

## 输出格式 ##

一个整数代表排列的逆序数。

## 输入样例 ##

4  
3 2 3 2

## 输出样例 ##

**提示  
注意答案的数据范围。**

解题思路：借助归并排序（递归）的实现过程来求得逆序对，我们发现在归并两段有序的子序列的时候，如果在后半段试探时出现的值比在前半段试探时出现的值小的时候，那么前半段该值及其以后的值都会与后半段的该值构成逆序对，因此我们就可以利用该特性求得逆序对的数量了。

**代码**：

#include<iostream>
    using namespace std;
    long long ans; 
    int a[100005],temp[100005]; 
    void print(int a[],int n)
    { 
    	for(int i=1;i<=n;i++)
    	cout<<a[i]<<' ';
    	cout<<endl;
    }
    void Merge(int a[],int l,int m,int r)
    { 
    	int k,i,j;
    	k=l,i=l,j=m+1;
    	while(i<=m&&j<=r)
    	{ 
    		if(a[i]<=a[j])
    		temp[k++]=a[i++];
    		else//后半段的该值较小 
    		temp[k++]=a[j++],ans+=m-i+1;
    	}
    	while(i<=m)
    	temp[k++]=a[i++];
    	while(j<=r)
    	temp[k++]=a[j++];
    	for(i=l;i<=r;i++)
    	a[i]=temp[i];
    }
    void Msort(int a[],int l,int r)
    { 
    	if(l==r)
    	return;
    	int m=(l+r)/2;
    	Msort(a,l,m);
    	Msort(a,m+1,r);
    	Merge(a,l,m,r);
    }
    int main()
    { 
    	int n,i;
    	cin>>n;
    	for(i=1;i<=n;i++)
    	cin>>a[i];
    	Msort(a,1,n);
    	cout<<ans;
    	return 0;
    }