Ultra-QuickSort
| Time Limit: 7000MS | Memory Limit: 65536K | |
| Total Submissions: 70674 | Accepted: 26538 |
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
Source
题目意思：
对于给定的无序数组
求除经过多少次相邻的元素交换之后，可以使得数组升序
就是求一个数列的逆序数
对于给定的无序数组
求除经过多少次相邻的元素交换之后，可以使得数组升序
就是求一个数列的逆序数
方法一：
树状数组求解逆序数
从头到尾读入这些数，每读入一个数就更新树状数组，
查看它前面比它小的已出现过的有多少个数sum，
然后用当前位置减去该sum，
就可以得到当前数导致的逆序对数了。
把所有的加起来就是总的逆序对数。
查看它前面比它小的已出现过的有多少个数sum，
然后用当前位置减去该sum，
就可以得到当前数导致的逆序对数了。
把所有的加起来就是总的逆序对数。
code：
#include<queue>
#include<set>
#include<cstdio>
#include <iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define max_v 500005
int n;
struct node
{
int v;
int pos;
} p[max_v];
int c[max_v];
int re[max_v];
int maxx;
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int d)
{
while(x<=n)
{
c[x]+=d;
x+=lowbit(x);
}
}
int getsum(int x)
{
int res=;
while(x>)
{
res+=c[x];
x-=lowbit(x);
}
return res;
}
bool cmp(node a,node b)
{
return a.v<b.v;
}
int main()
{
while(~scanf("%d",&n))
{
if(n==)
break;
memset(c,,sizeof(c));
for(int i=;i<=n;i++)
{
scanf("%d",&p[i].v);
p[i].pos=i;
} sort(p+,p++n,cmp);
for(int i=;i<=n;i++)
{
re[p[i].pos]=i;//离散化
} long long ans=;
for(int i=;i<=n;i++)
{
update(re[i],);
ans+=(i-getsum(re[i]));//当前位置减去前面比它小的数的个数之和就是答案
}
printf("%lld\n",ans);
}
return ;
}
/*
题目意思：
对于给定的无序数组
求除经过多少次相邻的元素交换之后，可以使得数组升序
就是求一个数列的逆序数 从头到尾读入这些数，每读入一个数就更新树状数组，
查看它前面比它小的已出现过的有多少个数sum，
然后用当前位置减去该sum，
就可以得到当前数导致的逆序对数了。
把所有的加起来就是总的逆序对数。
*/
感觉自己的树状数组这样写真的是傻的一批，离散化写的麻烦了，照着别人的离散化写的！
现在明白了离散化是什么东西：就是数据范围压缩！！！
贴一个自己离散化的代码
#include<queue>
#include<set>
#include<cstdio>
#include <iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define max_v 500005
int n;
struct node
{
int v;
int pos;
} p[max_v];
int c[max_v];
int re[max_v];
int maxx;
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int d)
{
while(x<max_v)
{
c[x]+=d;
x+=lowbit(x);
}
}
int getsum(int x)//返回1到x中小与等于x的数量
{
int res=;
while(x>)
{
res+=c[x];
x-=lowbit(x);
}
return res;
}
bool cmp(node a,node b)
{
if(a.v!=b.v)
return a.v<b.v;
else
return a.pos<b.pos;
}
int main()
{
while(~scanf("%d",&n))
{
if(n==)
break;
memset(c,,sizeof(c));
for(int i=;i<=n;i++)
{
scanf("%d",&p[i].v);
p[i].pos=i;
} sort(p+,p++n,cmp); long long ans=;
for(int i=;i<=n;i++)
{
ans+=(i-getsum(p[i].pos)-);//先找再更新，避免getsum的时候算上自己
update(p[i].pos,);
}
printf("%lld\n",ans);
}
return ;
}
方法二：归并排序求解逆序数
在归并排序的过程中，比较关键的是通过递归，
将两个已经排好序的数组合并，
此时，若a[i] > a[j]，则i到m之间的数都大于a[j]，
合并时a[j]插到了a[i]之前，此时也就产生的m-i+1个逆序数，
而小于等于的情况并不会产生。
code：
#include<stdio.h>
#include<memory>
#define max_v 500005
typedef long long LL;
LL a[max_v];
LL temp[max_v];
LL ans;
void mer(int s,int m,int t)
{
int i=s;
int j=m+;
int k=s;
while(i<=m&&j<=t)
{
if(a[i]<=a[j])
{
temp[k++]=a[i++];
}else
{
ans+=j-k;//求逆序数
temp[k++]=a[j++];
}
}
while(i<=m)
{
temp[k++]=a[i++];
}
while(j<=t)
{
temp[k++]=a[j++];
}
}
void cop(int s,int t)
{
for(int i=s;i<=t;i++)
a[i]=temp[i];
}
int megsort(int s,int t)
{
if(s<t)
{
int m=(s+t)/;
megsort(s,m);
megsort(m+,t);
mer(s,m,t);
cop(s,t);
}
}
int main()
{
int n;
while(~scanf("%d",&n))
{
if(n==)
break;
ans=;
for(int i=;i<n;i++)
scanf("%lld",&a[i]);
megsort(,n-);
printf("%lld\n",ans);
}
return ;
}
/*
题目意思：
对于给定的无序数组
求除经过多少次相邻的元素交换之后，可以使得数组升序
就是求一个数列的逆序数 在归并排序的过程中，比较关键的是通过递归，
将两个已经排好序的数组合并，
此时，若a[i] > a[j]，则i到m之间的数都大于a[j]，
合并时a[j]插到了a[i]之前，此时也就产生的m-i+1个逆序数，
而小于等于的情况并不会产生。
*/