Minimum Inversion Number

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

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

线段树求逆序数，手撸。

先求初始序列的逆序数（nlogn），再推出所有情况，求的最小值。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define maxn 5005

struct Node

{

    int l,r;

    int sum;

} tree[maxn<<];

void build(int l,int r,int rt)

{

    tree[rt].l=l;

    tree[rt].r=r;

    tree[rt].sum=;

    if(tree[rt].l==tree[rt].r)

        return;

    int mid=(l+r)/;

    build(lson);

    build(rson);

}

void update(int x,int l,int r,int rt)

{

    if(tree[rt].l==x&&tree[rt].r==x)

    {

        tree[rt].sum++;

        return;

    }

    int mid=(l+r)/;

    if(x<=mid)

        update(x,lson);

    else

        update(x,rson);

    tree[rt].sum=tree[rt<<].sum+tree[rt<<|].sum;

}

int ans=;

int query(int L,int R,int l,int r,int rt)

{

    if(L>R)

        return ;

    if(L==tree[rt].l&&R==tree[rt].r)

    {

       // cout<<tree[rt].sum<<endl;

       return tree[rt].sum;

    }

    int mid=(l+r)/;

    if(R<=mid)

        return query(L,R,lson);

    else if(L>mid)

        return query(L,R,rson);

    else

    {

        return query(L,mid,lson)+query(mid+,R,rson);

    }

}

int num[];

int main()

{

    int n;

    while(scanf("%d",&n)!=EOF)

    {

        ans=;build(,n,);

        for(int i=; i<n; i++)

        {

            scanf("%d",&num[i]);

            num[i]++;

        }

        //cout<<tree[16].l<<'*'<<tree[16].r<<endl;

        for(int i=n-;i>=;i--)

        {

            //cout<<num[i]<<'&'<<endl;

            if(i!=n-)

                ans+=query(,num[i]-,,n,);

            //cout<<ans<<endl;

            update(num[i],,n,);

            //cout<<ans<<endl;

        }

        int res=ans;

        for(int i=;i<n-;i++)

        {

            res=res+n-num[i]-num[i]+;

            ans=min(res,ans);

        }

        printf("%d\n",ans);

    }

    return ;

}

巴特西

HDU_1394_Minimum Inversion Number_线段树求逆序数

Minimum Inversion Number

最新文章

热门文章