欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

51Nod 1019 逆序数 【分治】

程序员文章站 2022-05-08 18:06:12
...

51Nod 1019 逆序数

分治法

1019 逆序数

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

如2 4 3 1中,2 1,4 3,4 1,3 1是逆序,逆序数是4。给出一个整数序列,求该序列的逆序数。

 收起

输入

第1行:N,N为序列的长度(n <= 50000)
第2 - N + 1行:序列中的元素(0 <= A[i] <= 10^9)

输出

输出逆序数

输入样例

4
2
4
3
1

输出样例

4

 

刚拿到这个题的时候想简单了  直接暴力**  结果 TLE  然后就懵了  (手动笑哭) 暴力的先入为主的思想挥之不去 后来又想的从后往前排序   想一想  跟暴力差不多  时间复杂度还是N方  最后想到了 归并排序  如果 第二队的元素入列  第一组剩余元素个数就是第二个元素在 范围内的逆序数  这样就很简单的  代码也就是一个 改进后的 归并排序 废话不多说  上代码

#include<iostream>

using namespace std;

const int MAX_N = 50000+5;

int arr[MAX_N];
int temp[MAX_N];
int ans;

void slove(int left,int right){
	if(left < right){ 
		int mid = (left+right)/2;
		// 拆分 
		slove(left,mid);
		slove(mid+1,right);
		
		int i = left;
		int l = left;
		int j = mid +1;
	
		//将两个部分其中一个排完 
		while(i <= mid && j <= right){
			if(arr[i]<= arr[j]){
				temp[l++]=arr[i++];
			}else{
				temp[l++]=arr[j++];
				ans+= mid-i+1;
			}
		}
	
		//确保两个部分所有元素都排完	
		while(i <= mid){
			temp[l++] = arr[i++];
		}
		while(j <= right){
			temp[l++] = arr[j++];
		}
		
		//更新序列  为下一步排序做准备 
		for(i = left; i <= right;i++){
			arr[i] = temp[i];
		}
	}
}

int main()
{
	int n;
	scanf("%d",&n);
	for(int i = 0; i < n; i++){
		cin >> arr[i];
	}
	ans = 0;
	slove(0,n-1);
	printf("%d\n",ans);

	return 0;
}