[POJ2828] Buy Tickets(待续)

时间:2021-07-30 19:25:12

[POJ2828] Buy Tickets(待续)

题目大意:多组测试,每组给出\(n\)条信息\((a,b)\),表示\(b\)前面有\(a\)个人,顺序靠后的信息优先级高

Solution.1

由后向前看,每个遇到的都是确定位置的,最后的人选定的位置不会改变,同样因为是倒叙输入,在第\(i\)个人后插队,也就是说他的前面一定要留下\(i\)个空格。

形象一点就是这样:

[POJ2828] Buy Tickets(待续)

从后往前,去查找第一个大于所需要空白的位置。用线段树维护空格数目即可

Code.1

#include <iostream>
#include <cstdio>
#include <algorithm> const int N = 2e5 + 10; int n;
int a[N], b[N];
int num[N << 2], spa[N << 2]; inline void pushup(int cur){
spa[cur] = spa[cur << 1] + spa[cur << 1 | 1];
return;
} void build(int cur, int l, int r){
int mid = l + ((r - l) >> 1);
if(l == r){
spa[cur] = 1;
num[cur] = 0;
}else{
build(cur << 1, l, mid);
build(cur << 1 | 1, mid + 1, r);
pushup(cur);
}
} void update(int cur, int l, int r, int la, int lb){
if(l == r){
spa[cur] = 0;
num[cur] = lb;
}else{
int mid = l + ((r - l) >> 1); if(spa[cur << 1] >= la){
update(cur << 1, l, mid, la, lb);
}else{
update(cur << 1 | 1, mid + 1, r, la - spa[cur << 1], lb);
}
pushup(cur);
}
} inline void print(int cur, int l, int r){
int mid = l + ((r - l) >> 1);
if(l == r){
printf("%d ", num[cur]);
return;
}else{
print(cur << 1, l, mid); print(cur << 1 | 1, mid + 1, r);
}
return;
} int main(){ while(scanf("%d", &n) != EOF){
build(1, 1, n);
for(int i = 1; i <= n; ++i){
scanf("%d %d", &a[i], &b[i]);
a[i] ++;
}
for(int i = n; i; --i){
update(1, 1, n, a[i], b[i]);
}
print(1, 1, n);
printf("\n");
} return 0;
}

Solution.2

用splay优雅接上

Code.2