POJ 2299 Ultra-QuickSort 简单题解

Ultra-QuickSort

Time Limit: 7000MS		Memory Limit: 65536K
Total Submissions: 68874		Accepted: 25813

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

Sample Output

6

0

Source

Waterloo local 2005.02.05

题目大意：求一组数据的逆序对，有多组数据，每组数据以一个n开头，读入以0结尾。

做法：归并排序（裸题）

代码如下：

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define N 500007

 #define LL long long

 using namespace std;

 int n;

 LL a[N], b[N], ans;

 inline LL read()

 {

     LL s = ;

     char ch = getchar();

     while (ch < '' || ch > '')    ch = getchar();

     while (ch >= '' && ch <= '')     s = s *  + ch - '', ch = getchar();

     return s;

 }

 inline void merge(int l, int mid, int r)

 {

     int i = l, j = mid + ;

     for (int k = l; k <= r; k++)

         if (j > r || i <= mid && a[i] < a[j])    b[k] = a[i++];

         else b[k] = a[j++], ans += mid - i + ;

     for (int k = l; k <= r; k++)    a[k] = b[k];

 }

 inline void mergeSort(int a, int b)

 {

     int mid = (a + b) / ;

     if (a < b)

     {

         mergeSort(a, mid);

         mergeSort(mid + , b);

         merge(a, mid, b);

     }

 }

 int main()

 {

     while(scanf("%d", &n) && n != )

     {

         ans = ;

         for (int i = ; i <= n; i++)

             a[i] = read();

         mergeSort(, n);

         cout << ans << endl;

     }

 }

巴特西

POJ 2299 Ultra-QuickSort 简单题解

最新文章

热门文章