题目;http://acm.hdu.edu.cn/showproblem.php?pid=5493
题目大意,t组数据,n个人,n行每行分别是人的身高和这个人的左边或右边比他高的人的个数,输出符合条件的字典序最小的人排列的序列.
想到线段树就很好做了,记录空位,按顺序安放人的身高,和原来做的题目很相似
#include<cstdio>
#include<algorithm>
using namespace std;
struct point {
int h,k;
bool operator <(const point & a)const
{
return h<a.h;
}
};
point yj[];
int res[];
struct node{
int l,r,x;
};
node tree[*];
void build(int i,int left,int right)
{
tree[i].l=left;tree[i].r=right;
if (left==right)
{
tree[i].x=;
return ;
}
int mid=(left+right)>>;
build(i<<,left,mid);
build(i<<|,mid+,right);
tree[i].x=tree[i<<].x+tree[i<<|].x;
}
void update(int i,int ans,int num)
{
if (tree[i].l==tree[i].r)
{
tree[i].x=;
res[tree[i].l]=num;
return ;
}
int mid=(tree[i].l+tree[i].r)>>;
if (ans<=tree[i<<].x) update(i<<,ans,num);
else update(i<<|,ans-tree[i<<].x,num);
tree[i].x=tree[i<<].x+tree[i<<|].x;
}
int main()
{
int t,i,q=,n;
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
for (i=;i<=n;i++)
scanf("%d %d",&yj[i].h,&yj[i].k);
sort(yj+,yj+n+);
build(,,n);
int flag=;
for (i=;i<=n;i++)
{
int m=n-i;
int temp=m-yj[i].k;
if (temp<)
{
flag=;
break;
}
if (temp>yj[i].k) update(,yj[i].k+,yj[i].h);
else update(,temp+,yj[i].h);
}
printf("Case #%d: ",q++);
if (flag) printf("impossible\n");
else
{
for (i=;i<=n;i++)
{
if (i!=n) printf("%d ",res[i]);
else printf("%d\n",res[i]);
}
}
}
return ;
}