Hdu1394 minimum inversion number

Posted by yjjr's blog on February 6, 2018

HDU1394 Minimum Inversion Number

标签:线段树,树状数组

http://www.sakurasake.icoc.me/nd.jsp?id=7#_np=2_327

Time Limit: 2000/1000 MS(Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Problem Description

The inversion number of a given numbersequence a1, a2, ..., an is the number of pairs (ai, aj) that satisfy i < jand ai > aj.

For a given sequence of numbers a1, a2, ..., an, if we move the first m >= 0numbers to the end of the seqence, we will obtain another sequence. There aretotally 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 ofthe above sequences.

 

 

Input

The input consists of a number of testcases. Each case consists of two lines: the first line contains a positiveinteger n (n <= 5000); the next line contains a permutation of the nintegers from 0 to n-1.

 

 

Output

For each case, output the minimum inversionnumber on a single line.

 

 

Sample Input

10

1 3 6 9 0 8 5 7 4 2

 

 

Sample Output

16

 

 

Author

CHEN, Gaoli

 

 

Source

ZOJMonthly, January 2003

 

分析:快速求逆序数,暴力算法主要分为两步:穷举逆序数,通过公式推出结果

公式为sum=sum-a[i]+(n-a[i]-1)

第二步几乎不可能优化,所以可以使用线段树优化第一步,时间复杂度为O(n log n)

当然通过树状数组应该也可以,就没有写代码了2333

举个栗子

序列3,2,5,4,0,1

3之前没有数大于它本身,val[1]=0

2之前有3大于它,val[2]=1

5之前没有数大于它本身,val[3]=0

4之前有5大于它,val[4]=1

0之前有3,2,5,4,大于它,val[5]=4

1之前有3,2,5,4大于它,val[6]=5

所以实际上,每插入val[i],就查询在[val[i],n-1]之间的数的个数,依次累加即可

#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define LL(x) ((x)<<1)
#define RR(x) ((x)<<1|1)
inline int read()
{
    int f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
using namespace std;

struct Seg_Tree
{
    int left,right,val;
    int calmid()
    {
        return (left+right)/2;
    }
}tt[15000];

int val[5001];

void make(int left,int right,int idx)
{
    tt[idx].left=left;
    tt[idx].right=right;
    tt[idx].val=0;
    if(left==right)return;
    int mid=tt[idx].calmid();
    make(left,mid,LL(idx));
    make(mid+1,right,RR(idx));
}

int query(int left,int right,int idx)
{
    if(left==tt[idx].left&&right==tt[idx].right) return tt[idx].val;
    int mid=tt[idx].calmid();
    if(right<=mid)return query(left,right,LL(idx));
    else if(mid<left)return query(left,right,RR(idx));
    else return query(left,mid,LL(idx))+query(mid+1,right,RR(idx));
}

void change(int id,int idx)
{
    tt[idx].val++;
    if(tt[idx].left==tt[idx].right)return;
    int mid=tt[idx].calmid();
    if(id<=mid)
        change(id,LL(idx));
    else change(id,RR(idx));
}
int main()
{
    int i,n,sum;
    while(scanf("%d",&n)==1)
    {
        make(0,n-1,1);
        for(i=0;i<n;i++)sum=0;
        for(i=0;i<n;i++)
        {
            scanf("%d",&val[i]);
            sum+=query(val[i],n-1,1);
            change(val[i],1);
        }
        int ret=sum;
        for(i=0;i<n;i++)
        {
            sum=sum-val[i]+(n-val[i]-1);
            ret=min(ret,sum);
        }
        printf("%d\n",ret);
    }
    return 0;
}




本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr