Minimum Inversion Number

Minimum Inversion Number

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Submit Status

Description

The inversion number of a given number sequence a1, a2, …, an is the number of pairs (ai, aj) that satisfy i < j and ai > aj.

For a given sequence of numbers a1, a2, …, an, if we move the first m >= 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following:

a1, a2, …, an-1, an (where m = 0 – the initial seqence) 
a2, a3, …, an, a1 (where m = 1) 
a3, a4, …, an, a1, a2 (where m = 2) 
… 
an, a1, a2, …, an-1 (where m = n-1)

You are asked to write a program to find the minimum inversion number out of the above sequences.

Input

The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 5000); the next line contains a permutation of the n integers from 0 to n-1.  

Output

For each case, output the minimum inversion number on a single line.  

Sample Input

10
1 3 6 9 0 8 5 7 4 2  

Sample Output

16  

 #include <stdio.h>
 #include <algorithm> using namespace std; int a[];
 struct Node{
     int l,r,num;
 }tree[]; void Build(int n,int x,int y){
     tree[n].l = x;
     tree[n].r = y;
     tree[n].num = ;
     if(x == y){
         return;
     }
     int mid = (x + y) / ;
     Build(*n,x,mid);
     Build(*n+,mid+,y);
 } void Modify(int n,int x){
     int l = tree[n].l;
     int r = tree[n].r;
     int mid = (l + r) / ;
     if(x == l && x == r){
         tree[n].num = ;
         return;
     }
     if(x <= mid)    Modify(*n,x);
     else            Modify(*n+,x);
     tree[n].num = tree[*n].num + tree[*n+].num;
 } int Query(int n,int x,int y){
     int l = tree[n].l;
     int r = tree[n].r;
     int mid = (l + r) / ;
     int ans = ;;
     if(x == l && y == r)
         return tree[n].num;
     if(x <= mid)   ans += Query(*n,x,min(mid,y));
     if(y > mid)    ans += Query(*n+,max(mid+,x),y);
     return ans;
 }
 int main(){
     //freopen ("a.txt" , "r" , stdin ) ;
     int n,sum,ans;
     int i,j;     while(scanf("%d",&n) != EOF){
         sum = ;
         Build(,,n);
         for(i = ;i <= n;i++){
             scanf("%d",&a[i]);
             Modify(,a[i]);
             sum += Query(,a[i]+,n);
         }
         ans = sum;
         for(i = ;i < n;i++){
             sum = sum + (n -  - a[i]) - a[i];
             if(sum < ans)
                 ans = sum;
         }
         printf("%d\n",ans);
     }
 }