题目链接：
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1093 Accepted Submission(s): 566
题意：
给出n个人的高度,以及这个人前面或者后面有多少个比她高,现在让你求字典序最小的队列的身高;
思路：
排序后可以得到这个队列中比某个人高的总人数假设是num,如果num<k比这个总人数还多的话就不可能了;
然后我们把这个k变成前边的比她高的人数,这个k是min(k,num-k)这样保证了字典序最小;
然后就是求每个位置上的身高呢,将身高从小大排序,这就是相当于给了一个序列的逆序数,然后让你还原这个序列了;
从小到大贪心,对于每个人二分她的位置,确定后更新到树状数组中,复杂度O(n*log2n);
AC代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e5+10;
int n,ans[maxn],sum[maxn],hi[maxn];
struct node
{
int h,k,id;
}po[maxn];
int cmp(node a,node b){return a.h>b.h;}
int cmp1(node a,node b)
{
if(a.h==b.h)return a.k<b.k;
return a.h<b.h;
}
inline int lowbit(int x){return x&(-x);}
inline void update(int x)
{
while(x<=n)
{
sum[x]++;
x+=lowbit(x);
}
}
inline int query(int x)
{
int s=0;
while(x)
{
s+=sum[x];
x-=lowbit(x);
}
return s;
}
int main()
{
int t,Case=0;
scanf("%d",&t);
while(t--)
{
printf("Case #%d:",++Case);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&po[i].h,&po[i].k),po[i].id=i;
sort(po+1,po+n+1,cmp);
int flag=0,num=0;po[0].h=-1;
for(int i=1;i<=n;i++)
{
if(po[i].h!=po[i-1].h)num=i-1;
if(po[i].k>num){flag=1;break;}
hi[i]=num;
}
if(flag)printf(" impossible\n");
else
{
for(int i=1;i<=n;i++)po[i].k=min(po[i].k,hi[i]-po[i].k),sum[i]=0;
sort(po+1,po+n+1,cmp1);
for(int i=1;i<=n;i++)
{
int l=po[i].k+1,r=n;
while(l<=r)
{
int mid=(l+r)>>1;
if(mid-query(mid)>po[i].k)r=mid-1;
else l=mid+1;
}
ans[r+1]=po[i].h;
update(r+1);
}
for(int i=1;i<=n;i++)printf(" %d",ans[i]);
printf("\n");
}
}
return 0;
}
原文：http://www.cnblogs.com/zhangchengc919/p/5951261.html