【每日一题】3.2 求逆序对

题目描述

给定一个长度为 n的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i个和第 j个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。

输入格式
第一行包含整数 n，表示数列的长度。

第二行包含 n个整数，表示整个数列。

输出格式
输出一个整数，表示逆序对的个数。

数据范围 1≤n≤100000，
数列中的元素的取值范围 [1,109]。

输入样例：
6
2 3 4 5 6 1
输出样例：
5

求解

使用归并排序的方法，先分开，在合并的时候判断逆序对数
如要合并下面两个排好序的序列时

left指向1，right指向2，两者比较，若left指向的数字大于right，则逆序对数= mid - left +1 （因为若left指向的数大于right指向的数，则left之后的数字都大于left指向的数字）

代码

#include<iostream>using namespace std;typedef long long ll;int a[100001];
//int sum =0;void sorta(int a[], int start, int mid, int end, ll* sum){int left = start;int right = mid +1;int j=0;int temp[end - start +1];while(left<= mid && right <= end){//cout<<left<<right<<" "<<a[left]<<a[right]<<endl;if(a[left]>a[right]){//cout<<"sum: "<<*sum<<endl;(*sum)+= mid - left + 1 ;//cout<<mid<<left<<end<<endl;//cout<<"单个排序中："<<*sum<<endl;temp[j] = a[right];right++;}else{temp[j] = a[left];left++;}j++;}while(left <= mid){temp[j] = a[left];j++;left++;}while(right<= end){temp[j] = a[right];j++;right++;}for(j = 0 ; j< end- start +1 ; j++){a[start + j] = temp[j];}return;}ll merge(int a[], int start, int end){if(start>=end){return 0;}int mid = (start + end)>>1;ll sum =0 ;sum += merge(a, start, mid);sum += merge(a, mid+1, end);//cout<<"排序前"<<start<<" "<<end<<endl;sorta(a,start,mid, end, &sum);//cout<<sum<<endl;return sum;}ll mergesort(int a[], int n){//int sum =0;ll sum = merge(a, 0, n-1);return sum;
}int main(){int n;cin>>n;int i;for(i=0;i <n; i++){cin>>a[i];}ll sum = mergesort(a, n);cout<<sum<<endl;return 0;}