poj2299--B - Ultra-QuickSort（线段树，离散化）

Ultra-QuickSort Time Limit: 7000MS Memory Limit: 65536KTotal Submissions: 41215 Accepted: 14915

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.

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

 

题意：求出最小交换次数。使得数组变得有序（由小到大）。  也就是求出逆序数。这个题归并排序，树状数组。线段树又能够解，能够当做练手用

使用线段树解的话，由于给出的数值非常大。所以须要离散化。一開始直接使用map果断的超时了，仅仅能想一个更简便的离散的方法，使用结构体存下一開始的值k和它初始的序号（id1），sort对k进行排序。得到新的序号（id2），通过id1直接改变给出的数组。变为id2。这样仅仅用n + logn的时间就能够离散完毕，（注意要推断反复的值。反复的值共享一个id2）。至于线段树部分就是一个模板

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define LL __int64 #define maxn 600000 #define lmin 1 #define rmax n #define lson l,(l+r)/2,rt<<1 #define rson (l+r)/2+1,r,rt<<1|1 #define root lmin,rmax,1 #define now l,r,rt #define int_now LL l,LL r,LL rt struct node{ LL id1 , id2 ; LL k ; }p[maxn] ; LL cl[maxn<<2] , a[maxn] ; bool cmp(node a,node b) { return a.k < b.k ; } void push_up(int_now) { cl[rt] = cl[rt<<1] + cl[rt<<1|1] ; } void update(LL i,int_now) { if( i < l || i > r ) return ; if( i == l && i==r ) { cl[rt]++ ; return ; } update(i,lson); update(i,rson); push_up(now); return ; } LL query(int ll,int rr,int_now) { if( ll > r || rr < l ) return 0; if( ll <= l && r <= rr ) return cl[rt] ; return query(ll,rr,lson) + query(ll,rr,rson); } int main() { LL i , n , m , l , r , x , num ; while(scanf("%I64d", &m) && m) { for(i = 0 ; i < m ; i++) { scanf("%I64d", &a[i]); p[i].k = a[i] ; p[i].id1 = i ; } sort(p,p+m,cmp); int temp = -1 ; n = 0 ; for(i = 0 ; i < m ; i++) { if( p[i].k == temp ) p[i].id2 = n ; else { p[i].id2 = ++n ; temp = p[i].k ; } } for(i = 0 ; i < m ; i++) a[ p[i].id1 ] = p[i].id2 ; memset(cl,0,sizeof(cl)); num = 0 ; for(i = 0 ; i < m ; i++) { num += (i - query(1,a[i],root)); update(a[i],root); } printf("%I64d\n", num); } return 0; }

 

 

转载于:https://www.cnblogs.com/bhlsheji/p/5169945.html

相关资源：数据结构—成绩单生成器