Ultra-QuickSort
Time Limit: 7000MS | Memory Limit: 65536K |
Total Submissions: 24055 | Accepted: 8603 |
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
5
4
3
1
2
3
Sample Output
6
Source
Waterloo local 2005.02.05
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define MAX 500001
int n, a[MAX], t[MAX];
long long sum;
/* 歸并 */
void Merge(int l, int m, int r) {
/* p指向輸出區間 */
int p = 0;
/* i、j指向2個輸入區間 */
int i = l, j = m + 1;
/* 2個輸入區間都不為空時 */
while(i <= m && j <= r) {
/* 取關鍵字小的記錄轉移至輸出區間 */
if (a[i] > a[j]) {
t[p++] = a[j++];
/* a[i]後面的數字對于a[j]都是逆序的 */
sum += m - i + 1;
}else {
t[p++] = a[i++];
}
}
/* 将非空的輸入區間轉移至輸出區間 */
while(i <= m) t[p++] = a[i++];
while(j <= r) t[p++] = a[j++];
/* 歸并完成後将結果複制到原輸入數組 */
for (i = 0; i < p; i++){
a[l + i] = t[i];
}
}
/* 歸并排序 */
void MergeSort(int l, int r) {
int m;
if (l < r) {
/* 将長度為n的輸入序列分成兩個長度為n/2的子序列 */
m = (l + r) / 2;
/* 對兩個子序列分别進行歸并排序 */
MergeSort(l, m);
MergeSort(m + 1, r);
/* 将2個排好的子序列合并成最終有序序列 */
Merge(l, m, r);
}
}
int main() {
int i;
while(cin >> n) {
if (n == 0) break;
sum=0;
for(i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
MergeSort(0, n - 1);
printf("%I64d\n", sum);
}
return 0;
}