题目链接： [点击打开链接](http://acm.hdu.edu.cn/showproblem.php?pid=5493) 题意：有n个人排队，每个人都有一个独一无二的身高，告诉你每个人的身高和他前面或者后面的比他高的人的个数（到底是前是后是未知的）。 要求你还原原来的队列，并且字典序最小。 思路： 因为要求字典序最小， 我们可以先按照身高从小到大排序，假设当前到了第i高的人， 他前面或者后面有k个人， 那么他前面的所有人都比他矮， 比他高的还有n-i个人，那么假设他前面还有p个空位， 他就是第p+1个空位上的人， 那么怎么求p呢？  因为要求字典序最小， 所以 p = min(k, n - i - k)。 为什么这样是对的呢？每个人有两个可能位置啊， 因为他之前的都比他矮，  所以他无论在哪个位置都是可以的。 那么为了让字典序最小， 就选择一个较小的位置。   当n - i - k < 0 时， 说明没有多余空格， 那么无解。 为了加速算法， 二分第i个人的位置， 用树状数组判断他前面有多少人以此确定空余的位置数。    复杂度O(n*logn*logn)。 细节参见代码： ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int maxn = 100000 + 5; int T,n,m,bit[maxn],kase=0,ans[maxn]; struct node { int v, num; bool operator < (const node& rhs) const { return v < rhs.v; } }a[maxn]; int sum(int x) { int ans = 0; while(x > 0) { ans += bit[x]; x -= x & -x; } return ans; } void add(int x, int d) { while(x <= n) { bit[x] += d; x += x & -x; } } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); memset(bit, 0, sizeof(bit)); for(int i=1;i<=n;i++) { scanf("%d%d",&a[i].v,&a[i].num); } sort(a+1,a+n+1); bool ok = true; for(int i=1;i<=n;i++) { int k = min(a[i].num, n-i-a[i].num); int l = 1, r = n, mid; if(n - i - a[i].num < 0) { ok = false; break; } ++k; while(r > l) { mid = (r+l)/2; if(mid - sum(mid) >= k) r = mid; else l = mid + 1; } add(l, 1); ans[l] = a[i].v; } printf("Case #%d:",++kase); if(ok) { for(int i=1;i<=n;i++) { printf(" %d",ans[i]); } printf("\n"); } else printf(" impossible\n"); } return 0; } ~~~