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
分析：快速求逆序数，暴力算法主要分为两步：穷举逆序数，通过公式推出结果
公式为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;
}
