Time Limit: 7000MS | Memory Limit: 65536K | |
Total Submissions: 55716 | Accepted: 20578 |
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.
Ultra-QuickSort produces the output
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 0
Sample Output
6 0
Source
思路:
这道题问的是给你一个数列,求将数列进行升序排要操作多少次。
首先分析怎么求操作的次数。
例如9 1 0 5 4
先进行第一次排序 0 9 1 5 4 交换了2次,等于0的逆序数。
再进行排序 0 1 9 5 4 交换了1次,等于1的逆序数。
在进行排序 0 1 4 9 5 交换了2次,等于4的逆序数。
在进行排序 0 1 4 5 9 交换了1次,等于1的逆序数。
这样操作的次数为2 + 1 + 2 + 1 = 6,正好等于数列的逆序数和。
每次都要把数列中相对小的数向前移动,因为每次移动都是把小的放到大的前面,有几个大的就要移动几次,这正好是这个数的逆序数。所以,接下来就就是求逆序数了。
可以用两层循环求每一个数的逆序数,但是500,000*500,000会TLE。
主要是解决一个数他前面比他大的个数有几个。
转换一下求前面有多少个数比他小,用树状数组,我们用这个数作为树状数组的下标,每次向下标中放上1,统计他前面共有多少个数,这样就完美的解决了时间复杂度和逆序数的问题。
但是,另外一个问题出现了。如果这个数要是做下标,那么他的范围可是0 <= a[i] <= 999,999,999,所以在进行离散就ok了。
#include <cstdio> #include <set> #include <map> #include <vector> #include <cstring> #include <iostream> #include <algorithm> #define space " " using namespace std; const int MAXN = 500000 + 10; int n, ar[MAXN], b[MAXN], num[MAXN]; int sum(int x) { int s = 0; while (x >= 1) { s += num[x]; x -= x&-x; } return s; } void add(int x, int y) { while (x <= n) { num[x] += y; x += x&-x; } } int main() { while (scanf("%d", &n), n) { for (int i = 1; i <= n; i++) { scanf("%d", &ar[i]); b[i] = ar[i]; } memset(num, 0, sizeof(num)); sort(b + 1, b + 1 + n); long long ans = 0; for (int i = 1; i <= n; i++) { ar[i] = lower_bound(b + 1, b + 1 + n, ar[i]) - b; } // for (int i = 1; i <= n; i++) printf("%d %d ", i, ar[i]); for (int i = 1; i <= n; i++) { add(ar[i], 1); ans += i - sum(ar[i]); } printf("%lld ", ans); } return 0; }