poj 2828 Buy Tickets 【线段树点更新】

淡淡的烟草味﹌ 2022-08-13 13:57 58阅读 0赞

题目：[poj 2828 Buy Tickets][]

题意：有n个人排队，每个人有一个价值和要插的位置，然后当要插的位置上有人时所有的人向后移动一位当这个插入到这儿，如果没有直接插进去。

分析：分析发现直接插入移动的话花时间太多，我们可不可以用逆向思维。从后往前来，因为最后一个位置是肯定能确定的，而其他的则插入空的第某个位置。

比如第一组样例：

4
    0 77
    1 51
    1 33
    2 69

开始时候位置都为空 编号0 1 2 3

首先从最后一个来2 69

第二个位置空，则可以直接放

然后编号变为0 1 69 2

接着放1 33

编号变为 0 33 69 1

然后放1 51

编号变为0 33 69 51

然后放最后一个0 77

则最后结果为 77 33 69 51

可以发现该怎么搞了，就是直接用线段树来维护区间上的值，然后选择插入相应的位置即可。

AC代码：

#include <cstdio>
    #include <vector>
    #include <iostream>
    using namespace std;
    typedef long long LL ;
    const int N = 220000;
    
    struct Node
    {
        int l,r;
        int val,num;
    };
    Node tree[5*N];
    void build(int o,int l,int r)
    {
        tree[o].l = l,tree[o].r = r;
        if(l==r)
        {
            tree[o].val = 1;
            return ;
        }
        int mid = (l+r)/2;
        build(o+o,l,mid);
        build(o+o+1,mid+1,r);
        tree[o].val = tree[o+o].val + tree[o+o+1].val;
    }
    void update(int o,int num,int val)
    {
        //printf("%d %d %d %d\n",o,tree[o].l,tree[o].r,tree[o].val);
        if(tree[o].l==tree[o].r)
        {
            tree[o].num = val;
            tree[o].val = 0;
            return ;
        }
        if(tree[o+o].val>=num)
            update(o+o,num,val);
        else
            update(o+o+1,num-tree[o+o].val,val);
        tree[o].val = tree[o+o].val + tree[o+o+1].val;
    }
    vector<int> ans;
    void Yougth(int o)
    {
        if(tree[o].l==tree[o].r)
        {
            ans.push_back(tree[o].num);
            return ;
        }
        Yougth(o+o);
        Yougth(o+o+1);
    }
    pair <int,int> p[N];
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int n;
        while(~scanf("%d",&n))
        {
            build(1,1,n);
            for(int i=0;i<n;i++)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                x++;
                p[i] = make_pair(x,y);
            }
            for(int i=n-1;i>=0;i--)
                update(1,p[i].first,p[i].second);
            Yougth(1);
            for(int i=0;i<ans.size();i++)
                printf("%d%c",ans[i],i==(ans.size()-1)?'\n':' ');
            ans.clear();
        }
        return 0;
    }

[poj 2828 Buy Tickets]: http://poj.org/problem?id=2828