題目鏈接：?[點擊打開鏈接](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; } ~~~