hdu 1394 Minimum Inversion Number

hdu 1394 的传送门

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

题目大意：
给你一个n个数的排列，然后可以将第一个元素放到最后一个，求这n个数列的最小的逆序数Min；
解题思路：

它的逆序列个数是N个，如果把t[i]放到t[N]后面，逆序列个数会减少t[i]个，相应会增加N-(t[i]+1)个
如果暴力的话，估计会超时，所以就用线段数搞一下，，注意线段树只是一个工具，！！

上代码：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=5005;
int num[maxn];
struct
{
    int l, r, num;
} tree[4*maxn];

void build(int root, int l, int r)
{
    tree[root].l=l;
    tree[root].r=r;
    tree[root].num=0;
    if(l == r)
        return;
    int mid=(l + r)>>1;
    build(root<<1, l, mid);
    build(root<<1|1, mid+1, r);
}

void update(int root, int pos)
{
    if(tree[root].l == tree[root].r)
    {
        tree[root].num++;
        return;
    }
    int mid=(tree[root].l+tree[root].r)>>1;
    if(pos<=mid)
        update(root<<1, pos);
    else
        update(root<<1|1, pos);
    tree[root].num=tree[root<<1].num+tree[root<<1|1].num;
}

int query(int root, int L, int R)
{
    if(L <= tree[root].l && R >= tree[root].r)
        return tree[root].num;
    int mid=(tree[root].l+tree[root].r)/2,ret=0;
    if(L <= mid)
        ret += query(2*root, L, R);
    if(R>mid)
        ret+=query(2*root+1, L, R);
    return ret;
}
int main()
{

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