首页 > 代码库 > poj2299 Ultra-QuickSort
poj2299 Ultra-QuickSort
Ultra-QuickSort
| Time Limit: 7000MS | Memory Limit: 65536K | |
| Total Submissions: 55894 | Accepted: 20653 |
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
题目大意：
对于给定的n个互不相同的整数A[1-n],每次可以交换相邻的两个数，求需要交换多少次才能够使原序列成升序。n<500,000，0<=A[i]<=999,999,999。
输入：有多组，每组第一个数n，后面n行n个数，最后一行以0结束。
输出：每组一个数最少交换次数。
首先我们要知道逆序对的概念
对于相邻的两个元素，交换并不能改变他们和其他元素的逆序关系
所以交换操作就只有两种结果：
1.减少一组逆序对
2.逆序对数不变
肯定存在一种解法使得每次交换都减少一组逆序对
接下来的问题是找逆序对
可以用归并的方法
还可以用线段树（树状数组）
注意要用离散化
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <cstdio> 5 using namespace std; 6 7 #define lson l,m,rt<<1 8 #define rson m+1,r,rt<<1|1 9 10 const int maxn=500005;11 int N;12 int sum[maxn<<2];13 14 struct node15 {16 int a,id;17 bool operator<(const node p)const18 {19 return a<p.a;20 }21 }A[maxn];22 23 void pushup(int rt)24 {25 sum[rt]=sum[rt<<1]+sum[rt<<1|1];26 }27 28 void update(int p,int l,int r,int rt)29 {30 if(l==r)31 {32 if(p==l) sum[rt]++;33 return;34 }35 int m=(l+r)>>1;36 if(p<=m) update(p,lson);37 if(p>m) update(p,rson);38 pushup(rt);39 }40 41 int query(int L,int R,int l,int r,int rt)42 {43 if(L<=l&&r<=R) return sum[rt];44 int m=(l+r)>>1;45 int cnt(0);46 if(L<=m) cnt+=query(L,R,lson);47 if(R>m) cnt+=query(L,R,rson);48 return cnt;49 }50 51 52 int main()53 {54 while(scanf("%d",&N),N)55 {56 memset(sum,0,sizeof(sum));57 long long ans(0);58 for(int i=1;i<=N;i++)59 {60 scanf("%d",&A[i].a);61 A[i].id=i;62 }63 sort(A+1,A+N+1);64 for(int i=1;i<=N;i++)65 {66 int q=A[i].id;67 ans+=query(q+1,N,1,N,1);68 update(q,1,N,1);69 }70 printf("%lld\n",ans);71 }72 return 0;73 }
poj2299 Ultra-QuickSort
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。