HDOJ 1394 Minimum Inversion Number
http://acm.hdu.edu.cn/showproblem.php?pid=1394
線分ツリーの解法:
題意:(1つの配列の最初の要素をこの配列の末尾に移動するたびに)最小の逆シーケンス数を求めます.
注意:逆シーケンス数:1つの配列で、対数の前後の位置がサイズ順と逆、すなわち前の数が後の数より大きい場合、逆シーケンスと呼ばれます.1つの配列における逆シーケンスの総数をこの配列の逆シーケンス数と呼ぶ.
構想:まず初期配列の逆序数Sumを求め,次いで元の配列のi番目の要素x[0]を最後に移動するたびに(n−(x[i]+1))個のx[i]より小さい数をループし,x[i]個のx[i]より大きい数を減算すると新しいSum値が得られる.Sumの最小値を求めればいい~
線分ツリーの解法:
題意:(1つの配列の最初の要素をこの配列の末尾に移動するたびに)最小の逆シーケンス数を求めます.
注意:逆シーケンス数:1つの配列で、対数の前後の位置がサイズ順と逆、すなわち前の数が後の数より大きい場合、逆シーケンスと呼ばれます.1つの配列における逆シーケンスの総数をこの配列の逆シーケンス数と呼ぶ.
構想:まず初期配列の逆序数Sumを求め,次いで元の配列のi番目の要素x[0]を最後に移動するたびに(n−(x[i]+1))個のx[i]より小さい数をループし,x[i]個のx[i]より大きい数を減算すると新しいSum値が得られる.Sumの最小値を求めればいい~
#include<stdio.h>
#include<string.h>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define maxn 5555
int sum[maxn<<2];
int x[maxn];
void PushUp(int rt)
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void updata(int p,int l,int r,int rt)
{
int m;
if(l==r)
{
sum[rt]++;
return ;
}
m=(l+r)>>1;
if(p<=m)
updata(p,lson);
else
updata(p,rson);
PushUp(rt);
}
int query(int L,int R,int l,int r,int rt)
{
int m,ret=0;
if (L<=l&&r<=R)
{
return sum[rt];
}
m=(l+r)>>1;
if (L<=m)
ret+=query(L,R,lson);
if (R>m)
ret+=query(L,R,rson);
return ret;
}
int main()
{
int n;
while(scanf("%d",&n)==1)
{
int i,Sum=0,ret;
memset(sum,0,sizeof(sum));
for(i=0;i<n;i++)
{
scanf("%d",&x[i]);
Sum+=query(x[i],n-1,0,n-1,1);
updata(x[i],0,n-1,1);
}
ret=Sum;
for(i=0;i<n;i++)
{
Sum+=n-x[i]-x[i]-1;// (n-(x[i]+1)) x[i] , x[i] x[i]
ret=ret<=Sum?ret:Sum;
}
printf("%d
",ret);
}
return 0;
}