POJ 2299 Ultra-QuickSort
Ultra-QuickSort
Time Limit: 7000MS | Memory Limit: 65536K | |
Total Submissions: 70096 | Accepted: 26270 |
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
0
Sample Output
6
0
题意:求快速排序的次数
思路:分治归并求逆序数
之前一篇博客讲解的已经很详细了,在此不再啰嗦 (《 ==== 链接)
AC代码:
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
#define MAXN 500000+10
ll a[MAXN], ans[MAXN];
ll solve(int l, int r)
{
int mid = (l + r) >> 1;
if(l == r)
{
return 0;
}
ll num = 0;
num += solve(l, mid);
num += solve(mid + 1, r);
for(int i = l, j = mid + 1, k = 0; i <= mid || j <= r; k++)
{
if(i > mid) ans[k] = a[j++];
else if(j > r) ans[k] = a[i++];
else if(a[i] <= a[j]) ans[k] = a[i++];
else
{
ans[k] = a[j++];
num += mid - i + 1;
//printf("%lld*", num);
}
}
for(int i = 0; i <= (r - l); i++)
a[l + i] = ans[i];
return num;
}
int main()
{
int n;
while(scanf("%d", &n) != EOF && n)
{
for(int i = 0; i < n; i++)
{
scanf("%lld", &a[i]);
}
printf("%lld\n", solve(0, n-1));
memset(a, 0, sizeof(a));
memset(ans, 0, sizeof(ans));
}
return 0;
}
其实就是上一篇博客加一个循环,注意:每次都要对两个数组进行初始化