首页 > 代码库 > POJ2299（Ultra-QuickSort）
POJ2299（Ultra-QuickSort）
Ultra-QuickSort
| Time Limit: 7000MS | Memory Limit: 65536K | |
| Total Submissions: 43384 | Accepted: 15806 |
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 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
59105431230
Sample Output
60
这题毫无疑问是求逆序对了，这么多组数，如果用排序，直接OVER。
但是用高效的树状数组求逆序对，无疑是最好的方法。
不过要注意的是，也许数据会很大，所以，离散化是非常有必要的！
代码如下：
#include <stdio.h>#include <string.h>#include <math.h>#include <algorithm>using namespace std;int b[500000],n,m,k,a[500000];struct Node{ int a,b;}c[1000005];bool cmp(Node a,Node b){ return a.b<b.b;}int lowbit(int t){ return t&(-t);}int sum(int k) { int sum=0; while(k>0) { sum+=b[k]; k-=lowbit(k); } return sum;}void addorsub(int l,int d){ while(l<=n) { b[l]+=d; l+=lowbit(l); }}int main(){ __int64 i,s; while(~scanf("%d",&n)&&n) {memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); memset(a,0,sizeof(a)); for(i=1;i<=n;i++) {c[i].a=i; scanf("%d",&c[i].b); } sort(c+1,c+1+n,cmp);//排序 //下面就是离散化 a[c[1].a]=1;//c[i].b应该是最小的了，所以不妨令a[c[i].a]为1；（实际上c[i].a不一定是1） //然后，下面就可以使得其余的a数组的数跟着i变化，达到离散化！ for(i=2;i<=n;i++) { if(c[i].b!=c[i-1].b)//当然，遇到相同的数，不妨让他们相等。但是，此时可能某个数不存在了。 a[c[i].a]=i; else a[c[i].a]=a[c[i-1].a]; } s=0; for(i=1;i<=n;i++)//强大的求逆序对代码！ { addorsub(a[i],1); s+=sum(n)-sum(a[i]); } printf("%I64d\n",s);}return 0;}
POJ2299（Ultra-QuickSort）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。