洛谷P1908 逆序对

客官°小女子只卖身不卖艺 2022-05-30 06:44 155阅读 0赞

## 题目描述 ##

猫猫TOM和小老鼠JERRY最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。最近，TOM老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中ai>aj且i<j的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。

## 输入输出格式 ##

输入格式：

第一行，一个数n，表示序列中有n个数。

第二行n个数，表示给定的序列。

输出格式：

给定序列中逆序对的数目。

## 输入输出样例 ##

输入样例\#1： 复制

6
    5 4 2 6 3 1

输出样例\#1： 复制

## 说明 ##

对于50%的数据，n≤2500

对于100%的数据，n≤40000。

使用归并算法，当第一个序列（下标比第二序列小）下标为i的元素大于第二个序列下标为j的元素时，ans+=mid-i+1。意思是前面序列一共比第二个序列下标为j的元素大的有多少个。

#include<stdio.h>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    int num[40005];
    int tmp[40005];
    int n;
    int ans;
    
    
    
    void mergeSort(int left,int right)
    {
    	if (left == right)
    		return;
    	int mid = (left + right) / 2;
    	mergeSort(left, mid);
    	mergeSort(mid + 1, right);
    	int i = left; int j = mid + 1; int k = left;
    	while (i <= mid&&j <= right)
    	{
    		if (num[i] > num[j])
    			tmp[k++] = num[j++],ans+=mid-i+1;
    		else
    			tmp[k++] = num[i++];
        }
    
    	while (i<=mid)
    		tmp[k++] = num[i++];
    	while (j<=right)
    		tmp[k++] = num[j++];
    
    	for (int i = left; i <= right; i++)
    		num[i] = tmp[i];
    }
    
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	cin >> n;
    	for (int i = 1; i <= n; i++)
    		cin >> num[i];
    	mergeSort(1, n);
    	cout << ans;
    	return 0;
    }