POJ 2299 Ultra-QuickSort （归并排序、逆序数）

POJ 2299 Ultra-QuickSort （归并排序、逆序数）

Description

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence 9 1 0 5 4 ,Ultra-QuickSort produces the output 0 1 4 5 9 .Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

Input

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 – the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

Output

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

Sample Input

59105431230

Sample Output

60

题意

求把一个序列排序所需要的最小相邻交换次数。

思路

题目可以转化为求数组所有数字的逆序数之和，因为n比较大的关系，所以舍弃 O(n2)

一般这样的题目都可以用归并排序来解决，或者树状数组也可以。

假设当前归并排序的两个序列为

1 3 4 9

2 5 7 8

分别取数3、2，3>2，说明3后面所有的数都比2大(m-p)，因为序列1一定在序列2前面，那这一个解释便是逆序数咯！

另外，当序列2全部排序完之后序列1还剩9，此时可以得到，9以及后面的所有的数都比序列2大(y-m)。

AC 代码

#include #include#include#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。