HDU-1394: Minimum Inversion Number（逆序数）

线段树

Problem Description

The inversion number of a given number sequence $a_1, a_2, ..., a_n$ is the number of pairs $(a_i, a_j)$ that satisfy i < j and $a_i > a_j$.

For a given sequence of numbers $a_1, a_2, ..., a_n$, 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:

$a_1, a_2, ..., a_{n-1}, a_n$(where m = 0 - the initial seqence)
$a_2, a_3, ..., a_n, a_1$ (where m = 1)
$a_3, a_4, ..., a_n, a_1, a_2$ (where m = 2)
...
$a_n, a_1, a_2, ..., a_{n-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

题意：输入n个数，然后按照题目要求交换这n个数的位置，求最小的逆序数是多少。
交换的法则，m从0到n-1变化，每次将第一个数拿到最后，如下：
$a_1, a_2, ..., a_{n-1}, a_n$ $（m=0，也就是初始的序列）$
$a_2, a_3, ..., a_n, a_1$ $（m=1）$
$a_3, a_4, ..., a_n, a_1, a_2$ $（m=2）$
...
$a_n, a_1, a_2, ..., a_{n-1}$ $（m=n-1）$

求在这n个序列中逆序数最小是多少。

分析：先用线段树求出最初的逆序数，（也可以归并求出），再循环n-1次，逆序数有这么一个规律：
原来的逆序数是ans,把a[0]移到最后之后，减少逆序数a[0]，同时增加逆序数n-a[0]-1个，总的变化ans-a[0]+n-a[0]-1。
因此每次的逆序数ans=ans-a[i]+n-a[i]-1，求出最小的即可。

• 完整代码：

#include<stdio.h>
#include<algorithm>
#define maxn 5005
using namespace std;
int a[maxn];
struct node
{
    int l,r,sum;
}s[4*maxn];
void build(int id,int l,int r)
{
    s[id].l=l;
    s[id].r=r;
    if(l==r)
        s[id].sum=0;
    else
    {
        int mid=(l+r)/2;
        build(id*2,l,mid);
        build(id*2+1,mid+1,r);
        s[id].sum=0; 
    }
}
void rep(int id,int x,int y)//y=1
{
    if(s[id].l==s[id].r)
        s[id].sum=y;
    else
    {
        int mid=(s[id].l+s[id].r)/2;
        if(x<=mid)
            rep(id*2,x,y);
        else
            rep(id*2+1,x,y);
        s[id].sum=s[id*2].sum+s[id*2+1].sum;
    }
}
int sum(int id,int l,int r)
{
    if(l<=s[id].l&&s[id].r<=r)
        return s[id].sum;
    else
    {
        int mid=(s[id].l+s[id].r)/2;
        if(r<=mid)
            return sum(id*2,l,r);
        else if(l>mid)
            return sum(id*2+1,l,r);
        else
            return sum(id*2,l,r)+sum(id*2+1,l,r);
    }
}
int main()
{
    int n,ss,ans;
    while(scanf("%d",&n)!=EOF)
    {
        ss=0;
        build(1,0,n-1);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            ss+=sum(1,a[i],n-1);
            rep(1,a[i],1);
        }
        ans=ss;//初始的逆序数
       // printf("%d\n",ans);
        for(int i=0;i<n;i++)
        {
            ans=min(ans,ss-a[i]+n-a[i]-1);
            ss=ss-a[i]+n-a[i]-1;
        }
        printf("%d\n",ans);
    }
    return 0;
}