POJ 2828 Buy Tickets 线段树 单点修改记录状态

tyvj上清北学堂入学测试引用的一道题
本来看到插队以为是队列2333 各种被坑QAQ 最后在各路大神的调教下用线段树解决QwQ

题目大意： 多组数据，给出几个人插队的要求和他们的权值 ，求最后队伍的排列情况，分组输出。 样例输入
4
0 77
1 51
1 33
2 69
4
0 20523
1 19243
1 3890
0 31492
样例输出
77 33 69 51
31492 20523 3890 19243

如果两人的要求相同，那么插队的优先级一定是后者优先(后入的能最后满足条件而插到之前与他要求相同的人）
样例一插队过程：
1.第一个人的要求是前面没有人，当前队列为空，可以插入，所以处于一号位
2.第二个人的要求是前面有一个人，刚好第一个人在前面，所以处于一号位之后，即二号位。
3.第三个人的要求是前面有一个人，但是，一号位二号位都有人，那么他只能插到二号位，所以二号位变为第三个人，而第二个人只能被挤下去三号位
4.最后一个插队的人要求前面有两个人，同理，他只能去三号位，所以第二个人就只能去四号位了。

做法就是利用线段树逆向进行单点修改
线段树记录的是当前区间内剩余的空位，如果某个人插入到n位置，则找第个n空位置插入即可

代码如下：

#include<cstdio>
#include<iostream>
using namespace std;
const int maxn = 200001;
struct node{
    int left,right;
    int sum;//存储空格
}tree[maxn*4];
int v,n,p[maxn],tv[maxn],a[maxn];
void update(int p)
{
    tree[p].sum = tree[p<<1].sum + tree[p<<1|1].sum;
}
void build(int l,int r,int now)
{
    tree[now].left = l;
    tree[now].right = r;
    if(r == l)
    {
        tree[now].sum = 1;//每个子节点均视为一个空位置
        return ;
    }
    int mid = (l + r) / 2;
    build(l,mid,now * 2);
    build(mid + 1,r,now * 2 + 1);
    update(now);
}
void change(int p,int now)
{
    if(tree[now].left == tree[now].right)
    {
        a[tree[now].left] = v;//插队后赋权值
        tree[now].sum = 0;//插队后该子节点没有空位置
        return ;
    }
    if(tree[now*2].sum >= p)
        change(p,now * 2);
    else 
        change(p - tree[now * 2].sum,now * 2 + 1);
        //判断插队的点的要求，如果左儿子的空位足够，则在左儿子中搜，否则就去右儿子中搜，且右边的空格数还需要等于当前编号减去左儿子的空格总数
    update(now);
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        build(1,n,1);
        for(int i = 1;i <= n;i ++)
            scanf("%d%d",&p[i],&tv[i]);
        for(int i = n;i >= 1;i --)
        {
            v = tv[i];
            change(p[i] + 1,1);//倒序插入，满足插队的优先级，即当前元素插入到第n个元素后，即将它放在剩余的空格中的第p+1格空格中。
        }
        for(int i = 1;i <= n;i ++)
            printf("%d ",a[i]);
        printf("n");
    }
    return 0;
}

最后

以上就是狂野钢笔为你收集整理的POJ 2828 Buy Tickets 线段树 单点修改记录状态的全部内容，希望文章能够帮你解决POJ 2828 Buy Tickets 线段树 单点修改记录状态所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。