首页 > 代码库 > poj 2299 Ultra-QuickSort(树状数组）
poj 2299 Ultra-QuickSort(树状数组）
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，n==0结束，接着输入n个数。把输入的数排好序需要几步。
思路：由于输入的数不是从1开始公差为1的递增序列，先用两个快排转换一下，代入树状数组就ok了！
ac代码：
#include<stdio.h>#include<iostream>#include<string.h>#include<algorithm>using namespace std;long long d1[5000000];int n;struct node //g存数，h存下标{ int g,h;} s[5000000];int cmp(struct node a,struct node b) //控制排序的方向从大到小{ return a.g>b.g;}int cmp1(struct node a,struct node b) //控制排序方向从小到大{ return a.h<b.h;}int lowbit(int x) { return x&(-x);}long long sum(int x) //树状数组求和，这题是求x前面有多少个数，因为把所有数转换成公差为1的递增序列，求出的和就是答案{ long long res=0; while(x>0) { res+=d1[x]; x-=lowbit(x); } return res;}void add(int x) //更新树状数组{ while(x<=n) { d1[x]++; x+=lowbit(x); }}int main(){ int a,b,i,j; long long num; while(scanf("%d",&n)!=EOF) { if(n==0) break; num=0; memset(d1,0,sizeof(d1)); for(i=1; i<=n; i++) { scanf("%d",&s[i].g); s[i].h=i; } sort(s+1,s+n+1,cmp); //按g值的大小排序 for(i=1; i<=n; i++) s[i].g=i; sort(s+1,s+n+1,cmp1); //按h排序 ，就是原来的下标 for(i=1;i<=n;i++) { num+=sum(s[i].g); //把这个数前面有的数的个数相加，就是答案 add(s[i].g); } printf("%lld\n",num); }} poj 2299 Ultra-QuickSort(树状数组）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。