链接:poj2299
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
5
9
1
0
5
4
3
1
2
3
0Sample Output
6
0题解
- 求逆序对数目
- 开一个大小为这些数的最大值的树状数组,并全部置0。从头到尾读入这些数,每读入一个数就更新树状数组,查看它前面比它小的已出现
- 过的有多少个数
- sum,然后用当前位置减去该sum,就可以得到当前数导致的逆序对数了。把所有的加起来就是总的逆序对数。
- 然而问题来了,数据最大999999999,显然开不下
- 解决方法是离散化一下
1 |
|