链接
http://poj.org/problem?id=2828
题意
有 $N$ 个人排队，每一个人都有一个权值 $val$ ，每一个人都会按顺序插入到当前队伍的某一个位置 $pos$。
要求按队伍最后顺序输出权值。
思路
从最后一个操作开始插入，每次插入即为最终位置，在插入的位置前还要留 $pos$ 个空位子。
树状数组维护空位子，二分查找插入位置。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <cstdio>
#include <iostream>
using namespace std;
const int N=2e5+5;
int n,a[N],val[N],x[N],y[N];
int lowbit(int x) {
return x&-x;
}
void update(int x) {
for(int i=x;i<=n;i+=lowbit(i)) ++a[i];
}
int query(int x) {
int ret=0;
for(int i=x;i;i-=lowbit(i)) ret+=a[i];
return ret;
}
int main() {
while(~scanf("%d",&n)) {
for(int i=1;i<=n;i++) a[i]=0;
for(int i=1;i<=n;i++) {
scanf("%d%d",&x[i],&y[i]);
++x[i];
}
for(int i=n;i>=1;i--) {
int l=x[i],r=n;
while(l<r) {
int mid=l+r>>1;
if(mid-query(mid)>=x[i]) r=mid;
else l=mid+1;
}
update(l);
val[l]=y[i];
}
for(int i=1;i<=n;i++) printf("%d ",val[i]);
puts("");
}
return 0;
}
|