[C++知识库]P1908 逆序对|C++

这个题目刚开始我想着用暴力解法，但是只过了三个点，得了25分，其他都超时，然后看了别人的解答，说是一道归并排序很典型的题目，因为归并排序的时候，分堆，然后需要把顺序错位的放入顺序正确的，这样每一轮的归并排序都可以解决一些逆序对，把所有的相加，就得到最终的答案。

• 暴力解法

#include <stdio.h>
#include <iostream>
#pragma warning(disable:4996);
const int maxn = 500050;
// 记录左边比他大，和右边比他小的数目，然后最后相加除2
int a[maxn];
int CountNum[maxn] = { 0 };
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	//统计
	for (int i = 0; i < n; i++) {
		//找左边大于这个数的
		for (int j = 0; j < i; j++) {
			if (a[j] > a[i]) {
				CountNum[i]++;
			}
		}
		//找右边小于这个数的
		for (int k = i + 1; k < n; k++) {
			if (a[k] < a[i]) {
				CountNum[i]++;
			}
		}
	}
	//统计有多少数
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		ans += CountNum[i];
	}
	printf("%d", ans / 2);
}

• 归并排序的解法

//mergeSort(int l,int r):归并排序，求到mid，然后就分成两边去归并排序
//排序返回后的两组数组都是有序的，再进行合并，合并到一个新的数组，每一个无序的时候，就需要加值在ans上
#include <stdio.h>
#include <iostream>
#pragma warning(disable:4996);
using namespace std;
const int maxn = 500050;
int a[maxn] = { 0 }; //原来的数组 用来存放数字
int temp[maxn] = { 0 };//暂时用来存储的数组
long long ans = 0;
void mergeSort(int l, int r)
{
	if (l >= r) {
		return;
	}
	int mid = (l + r) / 2;
	mergeSort(l, mid);
	mergeSort(mid + 1, r);
	int leftP = l;
	int rightP = mid + 1;
	int k = 0;
	while (leftP <= mid && rightP <= r)
	{
		if (a[leftP] <= a[rightP])
			temp[k++] = a[leftP++];
		else {
			temp[k++] = a[rightP++];
			ans = ans + mid - leftP + 1;
		}
	}
	while (leftP <= mid)
	{
		temp[k++] = a[leftP++];
	}
	while (rightP <= r)
	{
		temp[k++] = a[rightP++];
	}
	for (int i = 0, j = l; j <= r; i++, j++)
	{
		a[j] = temp[i];
	}
}
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	mergeSort(1, n);
	printf("%lld", ans);
}