HDU 1394 Minimm Inversion Number（正規並べ替え線分樹逆序数）
4149 ワード
http://acm.hdu.edu.cn/showproblem.php?pid=1394
DescriptionThe inversion number of a given number sequencea 1,a 2,…，an is the number of pairs(a i，a j)that satisfy i
For a given sequence of numbers a 1，a 2，…，a n，if we move the first m=0numbers to the end of the seqence，we will over Sequence.The are totallyn such sequences as:
a 1、a 2、…、an-1、an(where m=0-the initial seqence)a 2、a 3、…、an、a 1(where m=1)a 3、a 4、…、an、a 1、a 2(where m=2)an、a 1、a 2、…、an-1(where m=n-1)
You are asked to write a programto find the minimum inversion number out of the above sequences.
InputThe 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 11 3 6 9 0 8 7 4 2
Sample Output 16
件名:
n個が0からnまでの数が所定の順序で並べられていると、一番前の数だけ末尾に移動して各場合の逆の序数を算出し、逆の序数の最小値を求めることができます。
考え方:
正規並べ替えまたは線分ツリー
まず、現在の状況における逆の順序を求めます。
そして、n回のサイクルを繰り返すたびに、一番前の方に最後の方に移動します。ans=ans+(n-1+a[i])-a[i]
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
int num[5000+10],a[5000+10],t[5000+10];
//int vis[5000+10];
int ans;
void Merge(int x,int m,int y)
{
int p=x,q=m+1,i=x;
while(p<=m||q<=y)
{
if(q>y||(p<=m&&a[p]<=a[q])) t[i++]=a[p++];
else
{
t[i++]=a[q++];
ans+=m-p+1;
}
}
for(i=x;i<=y;i++) a[i]=t[i];
}
void mergesort(int x,int y)
{
if(x!=y)
{
int mid=(x+y)/2;
mergesort(x,mid);
mergesort(mid+1,y);
Merge(x,mid,y);
}
}
int main()
{
int n,i,j,minn;
while(scanf("%d",&n)!=EOF)
{
ans=0;
for(i=1;i<=n;i++)
{scanf("%d",&a[i]); num[i]=a[i];}
mergesort(1,n);
minn=ans;
for(i=1;i<n;i++)
{
ans=ans+n-1-2*num[i];
if(ans<minn) minn=ans;
}
cout<<minn<<endl;
}
return 0;
}
線分樹のバージョン
初期シーケンスについて
一つの数を加えるたびに、そのマークについて調べます。彼よりも大きな数が追加されていますか？逆の順序を求めます。
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#define mem(a,b) memset(a,b,sizeof(a))
#define ll __int64
#define MAXN 1000
#define INF 0x7ffffff
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
int sum[50000];
int a[5000+10];
void pushup(int rt)
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int l,int r,int rt)
{
if(l==r)
{
sum[rt]=0; return ;
}
int m=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
int getnum(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
return sum[rt];
}
int ret=0;
int m=(l+r)>>1;
if(L<=m) ret+=getnum(L,R,lson);
if(R>m) ret+=getnum(L,R,rson);
return ret;
}
void update(int num,int l,int r,int rt)
{
if(l==r&&l==num)
{
sum[rt]=1;
return ;
}
int m=(l+r)>>1;
if(num<=m) update(num,lson);
else update(num,rson);
pushup(rt);
}
int main()
{
int n;
int i,j;
int ans,minn;
while(scanf("%d",&n)!=EOF)
{
ans=0;
build(0,n-1,1);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
ans+=getnum(a[i],n-1,0,n-1,1);
update(a[i],0,n-1,1);
}
minn=ans;
for(i=0;i<n-1;i++)
{
ans=ans-a[i]*2+n-1;
if(minn>ans) minn=ans;
}
cout<<minn<<endl;
}
return 0;
}