给你n个人的身高和这n个人满足在他前面有k个人比他高或者在他后面有k个人比他高。问是否存在这样的序列,如果有输出字典序最小的排列(输出身高)。对于一个位置上放什么身高的人我们可以优先放身高小的,以由小到大逐个考虑,假设现在考虑第i个元素,有num个人要比他高,由于他前面的人都比他矮,因此可以全部忽略。这时候因为要考虑2种情况,那么我们优先选择会让第i个元素比较靠前的策略。如果是前面有num个人比他高,那么第i个人就在当前队列的第num+1个位置;如果后面有num个人比他高,由于当前队列长度缩减为了n-i+1,那么第i个元素在当前队列的位置就是(n-i+1)-num。然后取两者中的较小者即可。如果发现结果小于1,那么无解。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+4e4;
int S_Tree[maxn<<2];
int ans[maxn];

struct point{
	int h, num;
}arr[maxn];
int cmp(point x, point y){
	return x.h<y.h;
}
void S_Tree_build(int k, int l, int r){
    S_Tree[k] = r-l+1;
	if(l==r)
		return ;
    int mid=(l+r)>>1;
    S_Tree_build(k<<1, l, mid);
    S_Tree_build(k<<1|1, mid+1, r);
}
void point_change(int k, int l, int r, int x,int v){
    S_Tree[k]--;
	if(l==r){
		ans[l] = v;
		return ;
	}
    int mid=(l+r)>>1;
	if(S_Tree[k<<1] > x)
    	point_change(k<<1,l,mid,x,v);
    else
		point_change(k<<1|1,mid+1,r,x - S_Tree[k<<1],v);
}
int main(){
	int T,count=0;cin>>T;
	while(T--){
		int n;cin>>n;
		for(int i=1;i<=n;i++){
			scanf("%d%d",&arr[i].h,&arr[i].num);
		}
		sort(arr+1, arr+n+1, cmp);
		S_Tree_build(1,1,n);
		// for(int i=1;i<(n<<2);i++)
		// 	cout<<S_Tree[i]<<" ";
		// cout<<endl;
		int flag = 1;
		for(int i=1; i<=n&&flag; i++){
			int a=arr[i].num, b=arr[i].h;
            a=min(a,n-i-a);
            if(a<0)
				flag=false;
            else 
				point_change(1,1,n,a,b);
			// for(int i=1;i<(n<<2);i++)
			// 	cout<<S_Tree[i]<<" ";
			// cout<<endl;
		}
		printf("Case #%d: ", ++count);
        if(!flag)
			puts("impossible");
        else 
			for(int i=1; i<=n; ++i)
				printf("%d%c",ans[i],i==n?'\n':' ');
	}
	//system("pause");
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注