首页 > 代码库 > (离散化+树状数组求逆序数) poj 2299
(离散化+树状数组求逆序数) poj 2299
Ultra-QuickSort
| Time Limit: 7000MS | Memory Limit: 65536K | |
| Total Submissions: 44390 | Accepted: 16149 |
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<iostream>#include<cstdio>#include<cstring>#include<string>#include<cmath>#include<cstdlib>#include<algorithm>using namespace std;#define N 1000000int n,reflect[N],c[N];long long ans;struct node{ int val; int pos;}a[N];bool cmp(node a,node b){ return a.val<b.val;}int lowbit(int x){ return x&(-x);}int sum(int x){ int sum=0; while(x>0) { sum+=c[x]; x=x-lowbit(x); } return sum;}void add(int pos,int x){ while(pos<N) { c[pos]+=x; pos+=lowbit(pos); }}int main(){ while(scanf("%d",&n)!=EOF) { if(n==0) break; memset(reflect,0,sizeof(reflect)); memset(c,0,sizeof(c)); ans=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i].val); a[i].pos=i; } sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++) reflect[a[i].pos]=i; for(int i=1;i<=n;i++) { add(reflect[i],1); ans+=i-sum(reflect[i]); } printf("%I64d\n",ans); } return 0;}
(离散化+树状数组求逆序数) poj 2299
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。