赞
踩
Description
在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。
一个排列中逆序的总数就称为这个排列的逆序数。逆序数是课程线性代数的一个知识点。
现在给定一个排列a1,a2,…,an,如果存在i<j并且ai>aj,那么我们称ai和aj为一个逆序,请求出排列的逆序数。
输入格式
第一行为n,表示排列长度。(1=<n<=100000)
第二行有n个整数,依次为排列中的a1,a2,…,an。所有整数均在int范围内。
输出格式
一个整数代表排列的逆序数。
输入样例
4
3 2 3 2
输出样例
3
提示
注意答案的数据范围。
#include<iostream> using namespace std; int n,a[100005],temp[100005];//a是原数组,temp是临时数组 long long sum=0;//注意逆序数数据范围 void mergeSort(int left,int right) {//a、temp、sum都是全局变量可以不用传 if(right-left>1) { int mid = left+(right-left)/2; int temp_left=left,temp_right=mid,i=left; //temp_left和temp_right分别为左右两个待合并数组的遍历脚标,i为合并后数组的遍历脚标 //分治 mergeSort(left,mid); mergeSort(mid,right); //归并 while(temp_left<mid || temp_right<right) { if(temp_right>=right||(temp_left<mid&&a[temp_left]<=a[temp_right])) { temp[i++]=a[temp_left++];//[]和后置++优先级都为1,左结合 } else { temp[i++]=a[temp_right++]; sum += mid-temp_left;//在归并排序的基础上加上这一句 //当右数组的元素要往前排的时候左数组中有mid-temp_left个数比他大,构成逆序 }//明确"左右两个数组分别都是有序的"就不难理解这一方法了 } for(i=left; i<right; i++) {//从临时数组复制回原数组 a[i]=temp[i]; } } } int main() { ios::sync_with_stdio(0),cin.tie(0); int i; cin>>n; for(i=0; i<n; i++) { cin>>a[i]; } mergeSort(0,n); cout<<sum; return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。