此题采用线段树的做法
#include<bits/stdc++.h> using namespace std; struct nzy{ int h; int num; }a[100005]; struct oo{ int l,r; int data; }t[4*100005]; int store[100005]; bool cmp(nzy a,nzy b){ return a.h<b.h; } void build(int p,int l,int r){ t[p].l=l; t[p].r=r; if(t[p].l==t[p].r){ t[p].data=1; return; } int mid=(l+r)/2; build(2*p,l,mid); build(2*p+1,mid+1,r); t[p].data=t[2*p].data+t[2*p+1].data; } void ans(int p,int num,int h){ t[p].data--; if(t[p].l==t[p].r){ store[t[p].l]=h; return; } if(num<t[2*p].data) ans(2*p,num,h); else ans(2*p+1,num-t[2*p].data,h); } int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i].h; cin>>a[i].num; } sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++){ if(a[i].num>n-i){ printf("impossible"); return 0; } } build(1,1,n); for(int i=1;i<=n;i++){ ans(1,min(a[i].num,n-a[i].num-i),a[i].h); } for(int i=1;i<=n;i++){ printf("%d",store[i]); if(i!=n) putchar(' '); } return 0; }