C. Ultra-QuickSort

Time Limit: 7000ms

Memory Limit: 65536KB

64-bit integer IO format: 

%lld      Java class name: Main

 

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

59105431230

Sample Output

60 解题：求逆序数，归并排序或者快排+树状数组都可以。坑爹的地方在于要使用long long ,害我WA了几次。逗比。。。。。。 树状数组+快速排序

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #define LL long long13 #define INF 0x3f3f3f14 using namespace std;15 const int maxn = 500002;16 struct node {17 int val,index;18 } p[maxn];19 LL tree[maxn];20 bool cmp(const node &x,const node &y) {21 return x.val > y.val;22 }23 int lowbit(int x) {24 return x&(-x);25 }26 void update(int x,int val) {27 for(int i = x; i < maxn; i += lowbit(i)) {28 tree[i] += val;29 }30 }31 LL sum(int x) {32 LL ans = 0;33 for(int i = x; i; i -= lowbit(i)) {34 ans += tree[i];35 }36 return ans;37 }38 int main() {39 int n,i;40 LL ans;41 while(scanf("%d",&n),n) {42 for(i = 0; i < n; i++) {43 scanf("%d",&p[i].val);44 p[i].index = i+1;45 }46 sort(p,p+n,cmp);47 memset(tree,0,sizeof(tree));48 int pre = INT_MIN;49 for(ans = i = 0; i < n; i++) {50 update(p[i].index,1);51 ans += sum(p[i].index-1);52 53 }54 printf("%lld\n",ans);55 }56 return 0;57 }
                
               
              
             
            
           
          
         
        
       
      

归并排序

1 #include 
      
        2 #define LL long long 3 LL sum,dt[500010]; 4 void mysort(int lft,int rht,int step){ 5     static LL temp[500010]; 6     int md = lft + (step>>1),i = 0,k = 0,j = 0; 7     while(lft + i < md && md + j < rht){ 8         if(dt[lft+i] > dt[md+j]){temp[k++] = dt[md+j];j++; 9         }else{temp[k++] = dt[lft+i];i++;sum += j;}10     }11     while(lft+i < md){temp[k++] = dt[lft+i];i++;sum += j;}12     while(md+j < rht){temp[k++] = dt[md+j];j++;}13     for(i = 0; i < k; i++) dt[lft+i] = temp[i];14 }15 void ms(int n){16     int len = 1,step = 2,m,i,u,v;17     sum = 0;18     while(len < n){len <<= 1;}19     m = len/step;20     while(step <= len){21         for(i = 0; i < m; i++){22             u = i*step;v = (i+1)*step;23             mysort(u,v>n?n:v,step);24         }25         step <<= 1;m = len/step;26     }27 }28 int main(){29     int n,i;30     while(scanf("%d",&n),n){31         for(i = 0; i < n; i++)32             scanf("%d",dt+i);33         ms(n);34         printf("%lld\n",sum);35     }36     return 0;37 }