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;
}