poj 2828 Buy Tickets

本文从WordPress迁移而来, 查看全部WordPress迁移文章

线段树

题意:输入n有n个人排队,下面n行,每行第1个数字表示这个人想插队的位置(那个数字表示他插入后他前面有多少人,如果是0的话说明他插入后他是第1位,他前面没人),后面那个数字只是个标号,相当于他的名字吧,你要输出n个人插队后,队伍的状态,从头到尾输出那些人的名字

这题要从后面考虑,最后那个人,他插完队了,那么他的位置是固定的,就在那里,可见他不受前面任何一个人的影响。看看倒数第2个人,其实他插入的位置是有可能受到倒数第1个人的影响的,但是不受前面任何人的影响。逆回来插入人,看看他要位于哪个位置p(0即位于第一位,1即位于第二位………),然后从第1个位置开始数,数到第p个空位置(注意是空的才计数),那么就是他最后插入的地方。

所以线段树要维护的信息就是,一个区间内有多少空位置,对于一个人准备插入的时候,就是在总区间[1,n]内找到第p个空位置,然后插入,标记这个位置为占用了

用G++提交超时…………..

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 200010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define lson(i) ((i)<<1)
#define rson(i) ((i)<<1|1)

struct SegTree{
int l,r,cnt;
SegTree(){}
SegTree(int _l,int _r){
l = _l; r = _r; cnt = r-l+1;
}
int mid(){
return (l+r)>>1;
}
}t[N<<2];
int n,pos[N],name[N],res[N];

void build(int rt,int a,int b){
t[rt] = SegTree(a,b);
if(a == b) return ;
int mid = t[rt].mid();
build(lson(rt),a,mid);
build(rson(rt),mid+1,b);
}

int query(int rt,int cnt){
if(t[rt].l == t[rt].r) return t[rt].l;
int lcnt = t[lson(rt)].cnt;
int rcnt = t[rson(rt)].cnt;
if(lcnt >= cnt)
return query(lson(rt),cnt);
else
return query(rson(rt),cnt-lcnt);
}

void PushUp(int rt){
t[rt].cnt = t[lson(rt)].cnt + t[rson(rt)].cnt;
}

void updata(int rt,int index){
if(t[rt].l == t[rt].r){
t[rt].cnt = 0;
return ;
}
int mid = t[rt].mid();
if(index <= mid)
updata(lson(rt),index);
else
updata(rson(rt),index);
PushUp(rt);
}

int main(){
//freopen("case.txt","r",stdin);
while(scanf("%d",&n)!=EOF){
for(int i = 0; i < n; i++){
scanf("%d%d",&pos[i],&name[i]);
pos[i]++;
}
cl(res,-1);
build(1,1,n);
for(int i = n-1; i >= 0; i--){
int index = query(1,pos[i]);
res[index] = name[i];
updata(1,index);
}
for(int i = 1; i <= n; i++){
printf("%d",res[i]);
if(i == n) puts("");
else printf(" ");
}
}
return 0;
}

其实问题就是每次都要找出第x个空位,这是可以用树状数组去实现的,用的是一种二分逼近的思想(和二分不同)

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
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 200010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,pos[N],name[N],c[N],ans[N];

inline int lowbit(int x){
return x&(-x);
}

int query(int K){
int res = 0,cnt = 0;
for(int i = 18; i >= 0; i--){
res += (1<<i);
if(res >= n || cnt + c[res] >= K)
res -= (1<<i);
else
cnt += c[res];
}
return res+1;
}

void del(int p){
while(p <= n){
c[p]--;
p += lowbit(p);
}
}

int main(){
while(scanf("%d",&n)!=EOF){
for(int i = 1; i <= n; i++){
scanf("%d%d",&pos[i],&name[i]);
pos[i]++;
c[i] = lowbit(i);
}
for(int i = n; i >= 1; i--){
int index = query(pos[i]);
ans[index] = name[i];
del(index);
}
for(int i = 1; i <= n; i++){
printf("%d ",ans[i]);
}
puts("");
}
return 0;
}