首页 > 代码库 > poj 2299
poj 2299
Ultra-QuickSort
Time Limit: 7000MS | Memory Limit: 65536K | |
Total Submissions: 40427 | Accepted: 14559 |
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.
Ultra-QuickSort produces the output
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
Waterloo local 2005.02.05
这个题目是要求逆序数的,不是求最少几次交换使得数组有序。
怎么求逆序数呢,有两个nlog(n)的方法。
方法一:比如有个序列 9 5 2 4 6,从大到小排序,大小相同时按下标大的排在前面。
然后初始化一个数组 0 0 0 0 0 则最大的9对应的下标为1,则在相应的数组上加1,变为 1 0 0 0 0当前数组前的数加起来就是逆序。此时逆序为0。
依次类推数组变为1 0 0 0 1,逆序为0+1;数组变为1 1 0 0 1,逆序为0+1+1;数组变为1 1 0 1 1,逆序为0+1+1+2;数组变为1 1 1 1 1 ,逆序为0+1+1+2+2;所以最后逆序为6。然后在求前n项和的时候有树状数组,使时间降为log(n)。
方法二:归并排序(此方法不再赘述,具体参看我的博客中转载的一篇如何求数组的逆序)
AC代码,树状数组做的:
#include<iostream> #include<algorithm> #include<cstring> using namespace std; struct Node{ long long num; int index; }a[500010]; int b[500010]; int n; int cmp(Node t1,Node t2){ if(t1.num==t2.num) return t1.index>t2.index; return t1.num>t2.num; } int lowbit(int x){ return x&-x; } int sum(int x){ int s=0; while(x){ s+=b[x]; x-=lowbit(x); } return s; } void add(int x){ while(x<=n){ b[x]++; x+=lowbit(x); } } int main(){ while(cin>>n,n){ long long result=0; for(int i=1;i<=n;i++){ cin>>a[i].num; a[i].index=i; } sort(a+1,a+1+n,cmp); memset(b,0,sizeof(b)); for(int i=1;i<=n;i++){ add(a[i].index); result+=sum(a[i].index); } cout<<result-n<<endl; } return 0; }
AC代码,归并排序做的:
#include<iostream> #include<algorithm> using namespace std; long long a[500010]; long long tmp[500010]; long long result; void merge_sort(int x,int y){ if(x>=y) return ; int mid=(x+y)>>1; merge_sort(x,mid); merge_sort(mid+1,y); int i=x; int j=mid+1; int t=1; while(i<=mid && j<=y){ if(a[i]<=a[j]){ tmp[t++]=a[i++]; } else{ tmp[t++]=a[j++]; result+=mid-i+1; } } while(i<=mid) tmp[t++]=a[i++]; while(j<=y) tmp[t++]=a[j++]; int tt=x; for(int k=1;k<t;k++){ a[tt++]=tmp[k]; } } int main(){ int n; while(cin>>n,n){ result=0; for(int i=0;i<n;i++) cin>>a[i]; merge_sort(0,n-1); //for(int i=0;i<n;i++) //cout<<a[i]<<' '; cout<<result<<endl; } return 0; }
poj 2299
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。