首页 > 代码库 > poj2299 Ultra-QuickSort
poj2299 Ultra-QuickSort
Ultra-QuickSort
| Time Limit: 7000MS | Memory Limit: 65536K | |
| Total Submissions: 43339 | Accepted: 15798 |
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 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
59105431230
Sample Output
60
自从高二以来好像只用线段树没有写过树状数组……随便拿个求逆序对的题练练手
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define pi 3.1415926535897932384626433832795028841971using namespace std;inline LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}struct dat{ int a,rnk;}a[500010];int d[500010];int c[500010];bool operator <(const dat &a,const dat &b){return a.a<b.a;}int n,cnt;LL ans;inline int lowbit(int x){return x&(-x);}inline int change(int x){ for (int i=x;i<=n;i+=lowbit(i)) c[i]++;}inline int query(int x){ int sum=0; for (int i=x;i;i-=lowbit(i)) sum+=c[i]; return sum;}int main(){ while (scanf("%d",&n)&&n) { for (int i=1;i<=n;i++) a[i].a=read(),a[i].rnk=i; sort(a+1,a+n+1); cnt=ans=0; a[0].a=-1; for (int i=1;i<=n;i++) { if (a[i].a!=a[i-1].a)cnt++; d[a[i].rnk]=cnt; } memset(c,0,sizeof(c)); for (int i=n;i>=1;i--) { ans+=query(d[i]); change(d[i]); } printf("%lld\n",ans); }}
poj2299 Ultra-QuickSort
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。