【参考BLOG】 点击打开链接
【题意】
给定N<105个人的序列,N个(height,k)二元组描述这个序列 height:=这个人的身高,k:=这个人的左边或者右边有k个人比他高 构造一个字典序最小的序列满足这些条件 【解题方法】 从高到低放或者从低到高放都可以,由于本题要输出字典序最小的序列,所以我们使用从低到高放 由于从低到高放,之后放进去的是都是比当前高的 考虑当前当前放进去的第i个人,要满足后来的(即比他高的)有恰好k个在他前面或者在他后面 考虑有后来的k个人在他前面就是前面预留出k个位置 考虑有后来的k个人在他后面,已经放了i−1个人,剩下有n−(i−1)个人,再放k个在后面,还有n−(i−1)−k个,再去掉自己 那么问题就转化成了前面预留n−(i−1)−k−1=>n−i−k个 由于要字典序最小的,小的尽量往前放,所以取个min(k,n−i−k),如果这个值为负了,那么就表示不能放,就是impossible了 接下来就是普通的线段树求第min(k,n−i−k)+1个位置放进去当前这个人,维护区间k位的个数,查询的时候同时维护一下ans数组就好了 【AC 代码】 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn=1e5+10; typedef pair<int,int>P;P a[maxn]; int n,ans[maxn]; struct node{ int l,r,sum; }Tree[maxn<<2]; void pushup(int rt) { Tree[rt].sum=Tree[rt*2].sum+Tree[rt*2+1].sum; } void Build(int l,int r,int rt) { Tree[rt].l=l,Tree[rt].r=r; Tree[rt].sum=Tree[rt].r-Tree[rt].l+1; if(l==r) return ; int mid=(l+r)/2; Build(l,mid,rt*2); Build(mid+1,r,rt*2+1); } void update(int k,int v,int rt){ --Tree[rt].sum; if(Tree[rt].l==Tree[rt].r){ ans[Tree[rt].l]=v; return ; } if(Tree[rt*2].sum>k) update(k,v,rt*2); else update(k-Tree[rt*2].sum,v,rt*2+1); pushup(rt); } int main() { int T,cas=1; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1; i<=n; i++){ scanf("%d%d",&a[i].first,&a[i].second); } Build(1,n,1); sort(a+1,a+n+1); bool flag=1; for(int i=1; i<=n; i++){ int k=a[i].second,v=a[i].first; k=min(k,n-k-i); if(k<0){ flag=0; break; } update(k,v,1); } if(!flag){ printf("Case #%d: impossible\n",cas++); }else{ printf("Case #%d:",cas++); for(int i=1; i<=n; i++){ printf(" %d",ans[i]); } printf("\n"); } } }