POJ_2828_Buy Tickets

题意：插队问题；

2016.5.20,复习这道题。

总结：线段树基础不牢，建树，更新尚不熟悉，注意加强理解记忆。

主要理解：（单点更新，逆序插入）

发生插队时，前面的队伍是连续没有空位的，即pos：2，1，这种情况不会出现，至少应该为pos：1，2，1

插入顺序是逆序的（最后插入的val的位置不会再发生变化），如果正序插入则每个val的顺序是动态的。

插入pos，那么在pos这个位置之前应该还有pos-1个空位。

访问右节点的时候注意pos要修改，改为pos-sum[rt]，即整个线段的第pos个空位，在下一个右儿子那的第pos-sum[rt]个空位。

void Insert(int pos,int val,int l,int r,int rt)

{

    if(l==r)

    {

        spare[rt]=0;

        seq[l]=val;

        return;

    }

    int mid=(r+l)>>1;

    if(pos<=spare[rt<<1])

        Insert(pos,val,l,mid,rt<<1);

    else

        Insert(pos-spare[rt<<1],val,mid+1,r,rt<<1|1);

    PushUp(rt);

}

代码：

#include<iostream>

#include<cstdio>

using namespace std;

#define N 200005

int spare[N<<2];

int seq[N];

void PushUp(int rt)

{

    spare[rt]=spare[rt<<1]+spare[rt<<1|1];

}

void build(int l,int r,int rt)

{

    if(l==r)

    {

        spare[rt]=1;

        return;

    }

    int mid=(l+r)>>1;

    build(l,mid,rt<<1);

    build(mid+1,r,rt<<1|1);

    PushUp(rt);

}

void Insert(int pos,int val,int l,int r,int rt)

{

    if(l==r)

    {

        spare[rt]=0;

        seq[l]=val;

        return;

    }

    int mid=(r+l)>>1;

    if(pos<=spare[rt<<1])

        Insert(pos,val,l,mid,rt<<1);

    else

        Insert(pos-spare[rt<<1],val,mid+1,r,rt<<1|1);

    PushUp(rt);

}

int main()

{

    int n,p[N],v[N];

    while(scanf("%d",&n)!=EOF)

    {

        build(1,n,1);

        int i;

        for(i=1;i<=n;i++)

        {

            scanf("%d%d",&p[i],&v[i]);

            p[i]++;

        }

        for(i=n;i>0;i--)

        {

            Insert(p[i],v[i],1,n,1);

        }

        for(i=1;i<=n;i++)

        {

            if(i!=n)

                printf("%d ",seq[i]);

            else

                printf("%d\n",seq[i]);

        }

　　　　　/*for(i=1;i<=n;i++)         //如果这样输出就会超时，线段树容易超时

        {
　　　　　　　printf("%d",seq[i]);

            if(i!=n)

                printf(" ");

            else

                printf("\n");

        }*/

} return 0; }

巴特西

POJ_2828_Buy Tickets

最新文章

热门文章