HDU 5493 Queue（二分+树状数组）
最后更新于：2022-04-01 15:53:00
题目链接： [点击打开链接](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;
}
~~~