Q - Queue HDU - 5493
Sample Input
3
3
10 1
20 1
30 0
3
10 0
20 1
30 0
3
10 0
20 0
30 1
Sample Output
Case #1: 20 10 30
Case #2: 10 20 30
Case #3: impossible
思路
利用插空的思想， 当我们考虑 某个人 要被放到那个位置上的时候， 考到 可能是比他 高到k个人在他的前边，也可能是比他高到人在他的后边，这个是我们可 把题上给我们的序列按照从身高从小的到大来排序，这我正考虑要某个要放哪的时候是不会受 前边人已经安排好为位置的人影响，，这操作之后这个题目看起来简单些，，，接着由于字典序最小，，，由于每个人的身高是从小到大排序的，所以我们在 决定某个人要被放到 那个位置的时候（这个时候有多个位置符合题意） 我们应该尽量的把这个人放置的越靠前位置越好（在这个位置是符合题意的时候）， 那么我们怎判断某个人因该放那个位置呢？？我们可以假设 我们要放置的是 第 i 个人，在他的前边或后边 有k个人比他高， 可以确定已经有 i - 1 个人已经被的位置已经被确定了，我们先讨论第一个中情况：在 i 这个人的前边有 k 个人比他高， ⚠️之前放置的人，都比他矮，所以我们要预留 k + 1个空位置（因为 i 这个人也要占一个位置），具体找这个位置，我们可以通过 二分查找 来查找 前缀区间和为 k + 1 的位置 ； 接下来我们讨论第二种情况：在 区间的尾部留 k空位置，那么在这个空位置的前边剩余的空位置为 n - i - k + 1 ， 这样在用二分 来查找 区间前缀和为 n - i - k + 1 的位置的下标，由于字典序最小我们应在两种情况的到的位置中取最小的情况，并在把这个位置 天上这个人的身高就行了。。。。。。。这样不断遍历循环讨论下去，就能得到答案了
代码
#include<stdio.h>
#include<string>
#include<string.h>
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const int MAXN=200000+5; //最大元素个数
int n;//元素个数
int c[MAXN],ans[MAXN]; //c[i]==A[i]+A[i-1]+...+A[i-lowbit(i)+1]
int lowbit(int i){return i&(-i);} //返回i的二进制最右边1的值
int sum(int x){ //返回A[1]+...A[i]的和
int sum = 0;
while(x){
sum += c[x];
x -= lowbit(x);
}
return sum;
}
void add(int x, int val){ //令A[i] += val
while(x <= n){
c[x] += val;
x += lowbit(x);
}
}
int find_(int x){ //二分查找
int l=1,r=n,mid;
while(l<r){
mid=(l+r)>>1;
int num=sum(mid);
if(num<x)
l=mid+1;
else
r=mid;
}
return l;
}
int Sch(int num) //二分查找空位数为num 的位置
{
int l = 1, r = n, ans;
while(l <= r)
{
int mid = (l + r) >> 1;
if(Sum(mid) >= num)
r = mid - 1, ans = mid;
else
l = mid + 1;
}
return ans;
}
struct node1{
ll h,v;
}a[MAXN];
ll b[MAXN];
bool cmp(node1 x,node1 y){
return x.h<y.h;
}
int main(){
int t;
t--;
cin>>t;
int kase=0;
while(t--){
kase++;
memset(c,0,sizeof(c));
memset(ans,0,sizeof(ans));
scanf("%lld",&n);
for(int i=1;i<=n;i++){
add(i,1);
scanf("%lld%lld",&a[i].h,&a[i].v);
}
sort(a+1,a+n+1,cmp);
int flag=1;
for(int i=1;i<=n;i++){
if(n-i-a[i].v<0) {flag=0;break;}
int p=min(a[i].v,n-i-a[i].v)+1; //前面有多少个空位，包括本身，所以+1
int pos=find_(p);
add(pos,-1);
ans[pos]=a[i].h;
}
printf("Case #%d:", kase);
if (flag) {
for (int i = 1; i <= n; i++) {
printf(" %d", ans[i]);
}printf("\n");
}
else printf(" impossible\n");
}
return 0;
}
- 总结：1. 对待这种插空位置，我们应该按照一定的顺序，比如这一题 按身高从低到高 去一一的对待去讨论， 这样避免一些了复杂的东西。
- 2.这里的 “字典序最小” 与 “预留空位的操作” ，是奇妙的搭配
- 3.这一题的 树状数组 用来统计 空位置 的数量， 而一个又一个讨论找符合题意的下标位置 是很浪费时间的，所以加上了 一个快速 “二分” ， 快速查找就非常完美了