HDU 1394(Minimum Inversion Number)

spoiler posted @ 2011年4月12日 02:18 in ACM经典题目之线段树 , 1667 阅读

题目大意：给你一个连续的自然数序列，
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)

中逆序数最大的是多少。

其实用树状数组求这个是非常方便速度的，但是为了锻炼线段树我还是用线段树写了。

程序+部分注释：

#include<iostream>
#include<stdio.h>
using namespace std;
int ans=0;
struct node{
    int a,b;
    int v;
}s[20000];
 
int t[5002];
 
int Build(int x,int y,int num){
    s[num].a=x; s[num].b=y;
    s[num].v=0;
    if(x==y)
        return 0;
    Build(x,(s[num].a+s[num].b)/2,num+num);
    Build((s[num].a+s[num].b)/2+1,y,num+num+1); 
}
 
int modify(int num,int ide ){
    if(s[num].a==s[num].b){
        s[num].v=1;
        return 0;
    }
    else{
        if(ide<=(s[num].a+s[num].b)/2)
            modify(num+num,ide);
        else if(ide>(s[num].a+s[num].b)/2)
            modify(num+num+1,ide);
        s[num].v=s[num+num].v+s[num+num+1].v;
    }
}
 
int getsum(int x,int y,int num){
    if(x==s[num].a&&y==s[num].b){
        ans+=s[num].v;
        return 0;
    }
    else{
        if(y<=(s[num].a+s[num].b)/2)
            getsum(x,y,num+num);
        else if(x>(s[num].a+s[num].b)/2)
            getsum(x,y,num+num+1);
        else{
            getsum(x,(s[num].a+s[num].b)/2,num+num);
            getsum((s[num].a+s[num].b)/2+1,y,num+num+1);
        }
    }
}
 
int main(){
    int n,i,min;
    while(scanf("%d",&n)!=EOF){
        ans=0;
        for(i=1;i<=n;i++)
            scanf("%d",&t[i]);
        Build(1,n,1);
        for(i=n;i>=1;i--){
            getsum(1,t[i]+1,1);
            modify(1,t[i]+1);
                        求出总和
        }
        min=ans;
        for(i=1;i<=n-1;i++){
            ans=ans-t[i]+n-t[i]-1;
                        //因为数组是连续的自然数，从0到n所以
                       //t[i]移动到最后面去，就减少了t[i]个逆                    
                         //序对，同时也与以前是后面的而且比他大的数构成了
                           //N-（t[i]+1）组逆序对
            if(ans<min)
                min=ans;
        }
        printf("%d\n",min);
    }
    return 0;
}