POJ 2828-Buy Tickets

约定不等于承诺〃 2022-09-24 06:16 18阅读 0赞

POJ 2828 线段树

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #define lson rt<<1
    #define rson (rt<<1)+1
    using namespace std;
    int s[200001<<2];
    int a[200001],b[200001],c[200001];
    void build(int l,int r,int rt)
    {
        if(l==r)
        {
            s[rt]=1;
            return ;
        }
        int mid=(l+r)>>1;
        build(l,mid,lson);
        build(mid+1,r,rson);
        s[rt]=s[lson]+s[rson];
    }
    int query(int l,int r,int rt,int x)
    {
        int t;
        if(l==r)
        {
            s[rt]=0;
            return l;
        }
        int mid=(l+r)>>1;
        if(s[lson]>=x)
            t=query(l,mid,lson,x);
        else
            t=query(mid+1,r,rson,x-s[lson]);
        s[rt]=s[lson]+s[rson];
        return t;
    }
    int main()
    {
        int i,j,k,n,m,l;
        while(~scanf("%d",&n))
        {
            for(i=0;i<n;i++)
            {
                scanf("%d %d",&a[i],&b[i]);
            }
            build(1,n,1);
            for(i=n-1;i>=0;i--)
            {
                int t=query(1,n,1,a[i]+1);
             // printf("(%d)\n",t);
                c[t]=b[i];
            }
            for(i=1;i<=n;i++)
            {
                printf("%d ",c[i]);
            }
            printf("\n");
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，18人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode（Queue)2073. Time Needed to Buy Tickets

1.问题 There are n people in a line queuing to buy tickets, where the 0th person is at

以你之姓@/ 2023年09月25日 18:11/ 0 赞/ 9 阅读

相关 POJ 2828-Buy Tickets

POJ 2828 线段树 include<stdio.h> include<string.h> include<algorithm> defi

约定不等于承诺〃/ 2022年09月24日 06:16/ 0 赞/ 19 阅读

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

题目：[poj 2828 Buy Tickets][] 题意：有n个人排队，每个人有一个价值和要插的位置，然后当要插的位置上有人时所有的人向后移动一位当这个插入到这

淡淡的烟草味﹌/ 2022年08月13日 13:57/ 0 赞/ 59 阅读

相关 poj 1952 BUY LOW, BUY LOWER[最长单调子序列变形]

题目：[poj 1952 BUY LOW, BUY LOWER][poj 1952 BUY LOW_ BUY LOWER] 题意：给出一个序列，先求最长单调递减子序列，然后

阳光穿透心脏的1/2处/ 2022年08月08日 05:10/ 0 赞/ 10 阅读

相关 POJ 2828-Buy Tickets（线段树单点更新-插队）

Buy Tickets <table> <tbody> <tr> <td><strong>Time Limit:</strong> 4000MS<

红太狼/ 2022年06月17日 02:55/ 0 赞/ 142 阅读

相关 POJ 2828 Buy Tickets（线段树的单点更新）

Railway tickets were difficult to buy around the Lunar New Year in China, so we must get

偏执的太偏执、/ 2022年06月12日 14:23/ 0 赞/ 149 阅读

相关质量检验GB/T 2828

质检的检验方式有四种全检免检抽检需要GB2828 其他自定义检验比例 ![70][] ![70 1][] ![70 2][] ![70 3][

小咪咪/ 2022年05月17日 02:23/ 0 赞/ 175 阅读

相关 HDU-1260 Tickets（dp）

Problem Description: Jesus, what a great movie! Thousands of people are rushing to the

叁歲伎倆/ 2022年04月25日 05:10/ 0 赞/ 105 阅读

相关 Minimum Cost For Tickets

文章目录 Minimum Cost For Tickets 题目描述算法描述 C++实现 Scala实现

小鱼儿/ 2022年04月23日 09:06/ 0 赞/ 155 阅读

相关 POJ 2828 排队插队【线段树】题解

目录 1.题目 2.代码 1.题目 Railway tickets were difficult to bu

桃扇骨/ 2021年07月24日 19:50/ 0 赞/ 361 阅读