Jinglei's blog
0%

「POJ2299」Ultra-QuickSort

Posted on Edited on

题目链接 & 题面

题目链接

UVA（洛谷有RemoteJudge）-https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=20&page=show_problem&problem=1751

POJ-http://poj.org/problem?id=2299

AcWing-https://www.acwing.com/problem/content/109/

（不知道哪个是原创，都写上吧。。）

题目描述

在这个问题中，您必须分析特定的排序算法----超快速排序。

该算法通过交换两个相邻的序列元素来处理n个不同整数的序列，直到序列按升序排序。

对于输入序列9 1 0 5 4，超快速排序生成输出0 1 4 5 9。

您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。

输入格式

输入包括一些测试用例。

每个测试用例的第一行输入整数n，代表该用例中输入序列的长度。

接下来n行每行输入一个整数aia_i,代表用例中输入序列的具体数据，第i行的数据代表序列中第i个数。

当输入用例中包含的输入序列长度为0时，输入终止，该序列无需处理。

输出格式

对于每个需要处理的输入序列，输出一个整数op，代表对给定输入序列进行排序所需的最小交换操作数，每个整数占一行。

数据范围

0≤N<5000000≤N<500000,0≤N<5000000≤N<500000,
0≤ai≤9999999990≤a_i≤999999999

基本思路

逆序对

对于数组aa ，当其下标ii，jj 满足i<ji<j 且ai>aja_i > a_j 时，则称 aia_i 和 aja_j 构成逆序对。

例如序列9 1 0 5 4中，9和1是一对逆序对，9和0也是一对逆序对。

序列中，当逆序对的个数为0时，这个序列就是有序的，所以问题可以转化成“需要多少次交换可以将逆序对降为0”

交换两个相邻的逆序对时，序列的逆序对会减少1，这是因为，那两个相邻的数不再构成逆序对，并且它们和其它数的相对位置（不讨论距离）不变，和其它数构成的逆序对也不改变。

这样以来，只需要求出序列中逆序对的个数就可以知道需要交换几次。

归并排序

要求逆序对的个数，可以使用归并排序算法。

归并排序中，将一个序列拆成两半，并且左右两边排序之后，左半边任意一个数 和 右半边任意一个数 的相对位置并没有改变。

当左边的第 ii 个数大于右边第 jj 个数时，这两个数构成逆序对。

与此同时，左边的第 i+1i+1 ，i+2i+2 ……个数都大于 jj， 可以一次性统计。

有关归并排序算法，可以去听小甲鱼老师的 数据结构和算法：https://www.bilibili.com/video/BV1os41117Fs?p=95

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <iostream>
#define MAX 500005

int a[MAX], n;
long long ans;

void MergeSort(int*, int);

int main(){
//	freopen("data.in", "r", stdin);
	for( ; ; ){
		ans=0;
		scanf("%d", &n);
		if(n==0) return 0;
		for(int i=0; i<n; i++) scanf("%d", &a[i]);
		MergeSort(a, n);
		printf("%lld\n", ans);
	}
}

void MergeSort(int *arr, int len){
	if(len==1) return;

	int *l=arr, *r=arr+len/2;
	int ls=len/2, rs=len-len/2;
	MergeSort(l, ls);
	MergeSort(r, rs);

	int i=0, j=0, ts=0;
	int temp[MAX];
	while(i<ls && j<rs){
		if(l[i]>r[j]){
			temp[ts++] = r[j++];
			ans += ls-i;
		}
		else temp[ts++] = l[i++];
	}
	while(j<rs) temp[ts++] = r[j++];
	while(i<ls) temp[ts++] = l[i++];
	for(int x=0; x<ts; x++){
		arr[x] = temp[x];
	}
}