【参考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");
        }
    }
}