原题:
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
分析:注意到这里的n, n < 500,000 使用冒泡排序会超时,这时我们就需要一个更优秀的排序算法,
我们使用分治法的思想,归并排序法(merge sort),采用分治的思想,复杂度降为 nlongn 在n较大
的时候就变的快了很多很多了 。
以下是实现代码,需要一个额外的零时数组。
#include<iostream> #include<cstdio> using namespace std; long long cnt; void merge_sort(long long *A,long long *T,int x,int y) { if (y - x != 1){ int mid = x + (y - x) / 2; merge_sort(A, T, x, mid); merge_sort(A, T, mid, y); int i = x, j = mid, k = x; while (i < mid || j < y){ if (j >= y){ if (k>i){ cnt += (k - i); } T[k++] = A[i++]; continue; } if (i >= mid){ if (k>j){ cnt += (k - j); } T[k++] = A[j++]; continue; } if (A[i] <= A[j]){ if (k>i){ cnt += (k - i); } T[k++] = A[i++]; } else{ if (k>j){ cnt += (k - j); } T[k++] = A[j++]; } } for (int i=x; i < y; i++){ A[i] = T[i]; } } } long long A[500010], T[500010]; int main() { int t; while (scanf("%d", &t) && t != 0) { for (int i = 0; i < t; i++) { scanf("%d", A + i); } cnt = 0; merge_sort(A, T, 0, t); cout << cnt << endl; } return 0; }