Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

最小交换次数就是这个序列的逆序数,线代里有过证明,用归并排序就可以了

Posted by 110120_119 at 2019-04-01 15:41:27 on Problem 2299
/*
归并排序,求逆序数
*/

#include<cstdio>
#pragma warning (disable:4996)
using namespace std;

long long count = 0;	//逆序数
int arr[500010];
int temp[500010];		//辅助数组(暂时存放排序结果)

void merge(int arr[], int start, int medium, int end)		//start为第一段子序列的起点,medium为第一段的终点,medium+1为第二段的起点,end为第二段的终点,包括头尾
{
	int i = start, j = medium+1;			//i,j分别为两段的头指针,i从第一段的起点开始,j从第二段的起点开始
	int k = 0;
	while (i <= medium && j <= end)			//将两段子序列中的最短一段所有数字都比较完毕
	{
		if (arr[i] < arr[j])				//逐个将两个子序列中最小的数存放在辅助数组中
		{
			temp[k++] = arr[i++];
		}
		else
		{
			temp[k++] = arr[j++];
			count += medium - i + 1;		//逆序数核心!!!第一段尾减去第一段头,即为第二段插入元素当前的逆序数
		}
	}
	while (i <= medium)					//说明第一段元素没有全部比较完,将剩下元素全部放入辅助数组
	{
		temp[k++] = arr[i++];
	}
	while (j <= end)					//说明第二段元素没有全部比较完,将剩下元素全部放入辅助数组
	{	
		temp[k++] = arr[j++];		
	}
	for (int m = 0; m < k; m++)			//将原数组arr中顺序更新
	{
		arr[start++] = temp[m];			//注意数组从start开始更新,不是从0更新!!
	}
}

void mergeSort(int arr[],int start,int end)
{
	if (start == end)
		return;
	
	int medium = (start + end) / 2;

	mergeSort(arr,start,medium);			//递归调用自己
	mergeSort(arr, medium + 1, end);

	merge(arr, start, medium, end);
}

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	int n;
	while (scanf("%d", &n) != EOF && n != 0)
	{
		count = 0;
		for (int i = 0; i < n; i++)
			scanf("%d", &arr[i]);

		mergeSort(arr, 0, n - 1);
		printf("%lld\n", count);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator