【POJ】2299 - Ultra-QuickSort（离散化 & （树状数组 | 线段树））
【POJ】2299 - Ultra-QuickSort（离散化 & （树状数组 | 线段树））
点击打开题目
Ultra-QuickSort
Time Limit: 7000MS | Memory Limit: 65536K | |
|---|---|---|
Total Submissions: 54511 | Accepted: 20037 |
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
0Sample Output
6
0Source
Waterloo local 2005.02.05
刚开始一看时间，我去给了7s，那不是随便暴力嘛。
然后冒泡一遍过去，TLE。感觉被深深的欺骗了。
然后才知道了一个叫做归并排序的东西，知道什么叫逆序数。说白了就是让求逆序数。
举个例子说明一下：
第一组样例 ：
9 1 0 5 4
离散化一下：
1 2 3 4 5
排序都后的结果是：
0 1 4 5 9
3 2 5 4 1
那我们就从第一个数字看，0（3）表示它原来在第3位，也就是说有2个比它大的数，那么它的逆序数为2，然后把它删去；
然后是1（2），前面有1个比它大的，它的逆序数为1；
然后是4（5），前面有2个比它大的（因为之前已经把0和1删去了），它的逆序数为2。
一次类推，每个数对应的逆序数为：
0 1 4 5 9
2 1 2 1 0
把他们的逆序数相加求和就行了。
这里删数的时候，用树状数组或线段树来解决。ans要用__int64。（这道题树状数组要更快一些）
代码如下：（树状数组）
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
struct node
{
int num; //离散化之前
int trans; //离散化之后
}num[500000+11];
int sum[500000+11];
int n;
bool cmp(node a , node b)
{
return a.num < b.num;
}
void add(int x,int y) //x位置加y
{
while (x <= n)
{
sum[x] += y;
x += x & (-x);
}
}
int cal(int x) //从1加到x
{
int t = 0;
while (x)
{
t += sum[x];
x -= x & (-x);
}
return t;
}
int main()
{
__int64 ans;
while (~scanf ("%d",&n) && n)
{
for (int i = 1 ; i <= n ; i++)
{
scanf ("%d",&num[i].num);
num[i].trans = i;
}
sort (num+1 , num+1+n , cmp);
memset (sum,0,sizeof (sum));
for (int i = 1 ; i <= n ; i++)
add(i,1); //初始化树状数组
ans = 0;
for (int i = 1 ; i <= n ; i++)
{
ans += cal(num[i].trans-1);
add(num[i].trans,-1);
}
printf ("%I64d\n",ans);
}
return 0;
}代码如下：（线段树）
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAX 500000
#define L o<<1
#define R o<<1|1
int n;
struct node
{
int num; //离散化之前
int trans; //离散化之后
}num[MAX+11];
struct TREE
{
int l,r,sum;
}tree[MAX<<2];
void PushUp(int o)
{
tree[o].sum = tree[L].sum + tree[R].sum;
}
void Build(int o,int l,int r)
{
tree[o].l = l;
tree[o].r = r;
if (l == r)
{
tree[o].sum = 1;
return;
}
int mid = (l + r) >> 1;
Build (L , l , mid);
Build (R , mid+1 , r);
PushUp(o);
}
void UpDate(int o,int x,int y) // x 位的值加 y
{
if (tree[o].l == tree[o].r)
{
tree[o].sum += y;
return;
}
int mid = (tree[o].l + tree[o].r) >> 1;
if (mid >= x) //在左半区间
UpDate (L , x , y);
else
UpDate (R , x , y);
PushUp(o);
}
int Query(int o,int x,int y) //从x加到y
{
if (tree[o].l == x && tree[o].r == y)
return tree[o].sum;
int mid = (tree[o].l + tree[o].r) >> 1;
if (mid >= y)
return Query(L,x,y);
else if (x > mid)
return Query(R,x,y);
else
return Query(L,x,mid) + Query(R,mid+1,y);
}
bool cmp(node a,node b)
{
return a.num < b.num;
}
int main()
{
__int64 ans;
while (~scanf ("%d",&n) && n)
{
for (int i = 1 ; i <= n ; i++)
{
scanf ("%d",&num[i].num);
num[i].trans = i;
}
sort (num+1 , num+1+n , cmp);
Build(1,1,n); //1到n建立线段树
ans = 0;
for (int i = 1 ; i <= n ; i++)
{
if (num[i].trans != 1)
ans += Query(1 , 1 , num[i].trans-1);
UpDate(1 , num[i].trans , -1);
}
printf ("%I64d\n",ans);
}
return 0;
}腾讯云开发者
