算法1：求逆序对数与显著逆序对数（归并排序）

90 阅读 0 评论 60 点赞

我是靠谱客的博主称心睫毛膏，最近开发中收集的这篇文章主要介绍算法1：求逆序对数与显著逆序对数（归并排序），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

写在前面：由本文开始记录本人的算法刷题之路，日后会不定期更新，欢迎讨论！本系列系本人原创，如需转载或引用，请注明原作者及文章出处。

求逆序对数问题是归并排序的基础问题，显著逆序对数则是逆序对数的升级版。POJ2299，POJ1804均是此类问题（但是个别细节不同，例如POJ2299需要将逆序对数变量num设为long long int型）。

一、求逆序对数

描述

对于一个长度为N的整数序列A，满足i < j 且 Ai > Aj的数对(i,j)称为整数序列A的一个逆序。请求出整数序列A的所有逆序对个数

输入

输入包含多组测试数据，每组测试数据有两行
第一行为整数N(1 <= N <= 20000)，当输入0时结束
第二行为N个整数，表示长为N的整数序列

输出

每组数据对应一行，输出逆序对的个数

样例输入 5 1 2 3 4 5 5 5 4 3 2 1 1 1 0 样例输出 0 10 0 解体思路

归并排序，大家看代码自行理解吧。

代码

#include<iostream>
#include<algorithm>
using namespace std;
int n, a[20010], temp[20010], num;

void merge(int begin, int mid, int end)
{
	int i = begin;
	int j = mid + 1;
	int k = begin;

	while (i <= mid && j <= end)
	{
		if (a[i] > a[j])
		{
			temp[k] = a[j];
			k++;
			j++;
			num += mid - i + 1;
		}
		else
		{
			temp[k] = a[i];
			k++;
			i++;
		}
	}

	while (i <= mid)
	{
		temp[k] = a[i];
		k++;
		i++;
	}

	while (j <= end)
	{
		temp[k] = a[j];
		k++;
		j++;
	}

	for (int p = begin; p <= end; p++)
		a[p] = temp[p];
}

void mergesort(int begin, int end)
{
	if (begin >= end)
		return;

	int mid = (begin + end) / 2;
	mergesort(begin, mid);
	mergesort(mid + 1, end);
	merge(begin, mid, end);
}

int main()
{
	while (1)
	{
		cin >> n;
		if (n == 0)
			break;

		for (int i = 0; i < n; i++)
			cin >> a[i];

		num = 0;
		mergesort(0, n - 1);

		cout << num << endl;
	}
	return 0;
}

二、求显著逆序对数

描述

对于一个长度为N的整数序列A，满足i < j 且 Ai > 2 * Aj的数对(i,j)称为整数序列A的一个显著逆序。请求出整数序列A的所有显著逆序对个数

输入

输入包含多组测试数据，每组测试数据有两行
第一行为整数N(1 <= N <= 20000)，当输入0时结束
第二行为N个整数，表示长为N的整数序列

输出

每组数据对应一行，输出显著逆序对的个数

样例输入 5 1 2 3 4 5 5 5 4 3 2 1 6 12 10 8 6 4 2 0 样例输出 0 4 6

解体思路

与求逆序对数不同，由于Ai > 2 * Aj，因此需要将排序和计数分别操作。也就是先做count，再做merge。

代码

#include<iostream>
#include<algorithm>
using namespace std;
int n, a[20010], temp[20010], num;

void mcount(int begin, int mid, int end)
{
	int i = begin;
	int j = mid + 1;
	int k = begin;
	while (i <= mid && j <= end)
	{
		if (a[i] > 2 * a[j])
		{
			num += mid - i + 1;
			j++;
		}
		else
			i++;
	}
}

void merge(int begin, int mid, int end)
{
	int i = begin;
	int j = mid + 1;
	int k = begin;

	while (i <= mid && j <= end)
	{
		if (a[i] > a[j])
		{
			temp[k] = a[j];
			k++;
			j++;
		}
		else
		{
			temp[k] = a[i];
			k++;
			i++;
		}
	}

	while (i <= mid)
	{
		temp[k] = a[i];
		k++;
		i++;
	}

	while (j <= end)
	{
		temp[k] = a[j];
		k++;
		j++;
	}

	for (int p = begin; p <= end; p++)
		a[p] = temp[p];
}

void mergesort(int begin, int end)
{
	if (begin >= end)
		return;

	int mid = (begin + end) / 2;
	mergesort(begin, mid);
	mergesort(mid + 1, end);
	mcount(begin, mid, end);
	merge(begin, mid, end);
}

int main()
{
	while (1)
	{
		cin >> n;
		if (n == 0)
			break;

		for (int i = 0; i < n; i++)
			cin >> a[i];

		num = 0;
		mergesort(0, n - 1);

		cout << num << endl;
	}

	return 0;
}