# 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

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

#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)
{
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;
}