HDU 1394 Minimum Inversion Number (归并排序 | 线段树 | 数状数组)

Minimum Inversion Number

http://acm.hdu.edu.cn/showproblem.php?pid=1394

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5566 Accepted Submission(s): 3411

Problem 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

Author

CHEN, Gaoli

Source

ZOJ Monthly, January 2003

线段树解法：

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

#define L(rt) (rt<<1)
#define R(rt) (rt<<1|1)

const int N=5010;

struct Tree{
    int l,r;
    int cnt;
}tree[N<<2];

void PushUp(int rt){
    tree[rt].cnt=tree[L(rt)].cnt+tree[R(rt)].cnt;
}

void build(int L,int R,int rt){
    tree[rt].l=L;
    tree[rt].r=R;
    tree[rt].cnt=0;
    if(tree[rt].l==tree[rt].r){
        //scanf("%d",&tree[rt].x);
        return ;
    }
    int mid=(L+R)>>1;
    build(L,mid,L(rt));
    build(mid+1,R,R(rt));
}

void update(int id,int rt){
    if(tree[rt].l==tree[rt].r){
        tree[rt].cnt++;
        return ;
    }
    int mid=(tree[rt].l+tree[rt].r)>>1;
    if(id<=mid)
        update(id,L(rt));
    else if(id>=mid+1)
        update(id,R(rt));
    PushUp(rt);
}

int query(int L,int R,int rt){
    if(L==tree[rt].l && tree[rt].r==R)
        return tree[rt].cnt;
    int mid=(tree[rt].l+tree[rt].r)>>1;
    int ans=0;
    if(R<=mid)
        ans+=query(L,R,L(rt));
    else if(L>=mid+1)
        ans+=query(L,R,R(rt));
    else{
        ans+=query(L,mid,L(rt));
        ans+=query(mid+1,R,R(rt));
    }
    return ans;
}

int main(){

    //freopen("input.txt","r",stdin);

    int n,x[N];
    while(~scanf("%d",&n)){
        build(0,n-1,1);
        int ans=0;
        for(int i=0;i<n;i++){
            scanf("%d",&x[i]);
            ans+=query(x[i],n-1,1);
            update(x[i],1);
        }
        int tmp=ans;
        for(int i=0;i<n;i++){
            tmp+=n-1-x[i]-x[i];
            ans=min(ans,tmp);
        }
        printf("%d\n",ans);
    }
    return 0;
}

树状数组：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=5010;

int n,arr[N],num[N];

int lowbit(int x){
    return x&(-x);
}

void update(int id,int x){
    while(id<=N){
        arr[id]+=x;
        id+=lowbit(id);
    }
}

int Sum(int id){
    int ans=0;
    while(id>0){
        ans+=arr[id];
        id-=lowbit(id);
    }
    return ans;
}

int main(){

    //freopen("input.txt","r",stdin);

    while(~scanf("%d",&n)){
        memset(arr,0,sizeof(arr));
        int ans=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&num[i]);
            ans+=Sum(n+1)-Sum(num[i]+1);
            update(num[i]+1,1);
        }
        int tmp=ans;
        for(int i=1;i<=n;i++){
            tmp+=n-1-num[i]-num[i];
            ans=min(ans,tmp);
        }
        printf("%d\n",ans);
    }
    return 0;
}

归并排序：

#include<cstdio>
 #include<iostream>
 using namespace std;
 const int maxn=5005;
 int num1[maxn],num2[maxn],temp[maxn];
 int sum;
 void Merge(int l,int mid,int r){
     int p=0;
     int i=l,j=mid+1;
     while(i<=mid&&j<=r){
         if(num1[i]>num1[j]){
             sum+=mid-i+1;
             temp[p++]=num1[j++];
         }
         else temp[p++]=num1[i++];
     }
     while(i<=mid)temp[p++]=num1[i++];
     while(j<=r)temp[p++]=num1[j++];
     for(i=0;i<p;i++)
         num1[l+i]=temp[i];
 }
 void MergeSort(int l,int r){
     if(l<r){
         int mid=(l+r)>>1;
         MergeSort(l,mid);
         MergeSort(mid+1,r);
         Merge(l,mid,r);
     }
 }
 int main()
 {
     int n;
     while(~scanf("%d",&n)){
         for(int i=0;i<n;i++){
             scanf("%d",&num1[i]);
             num2[i]=num1[i];
         }
         sum=0;
         MergeSort(0,n-1);
         int ans=sum;
         for(int i=0;i<n-1;i++){
             sum+=n-num2[i]-num2[i]-1;
             ans=ans<sum?ans:sum;
         }
         printf("%d\n",ans);
     }
     return 0;
 }