poj 2828 Buy Tickets(动态队列·线段树单点更新)

2024-03-27 23:38

本文主要是介绍poj 2828 Buy Tickets(动态队列·线段树单点更新),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:http://poj.org/problem?id=2828

大意:一群人排队,第i个人来到队伍中站到处于posi的人的右边,且每个人都有不同的表示值,问最终的结果?

Sample Input

4
0 77
1 51
1 33
2 69
4
0 20523
1 19243
1 3890
0 31492

Sample Output

77 33 69 51
31492 20523 3890 19243

Hint

The figure below shows how the Little Cat found out the final order of people in the queue described in the first test case of the sample input.



能力低,感觉自己还得好好加油啊。。初读这题,感觉很厉害的样子,果然,想了很久还是没得到结果。参考了大神们的思路,总算有点头绪了。正确排序的关键是后来的有位置上的优先权:所以从后向前输入,用一颗二叉树的叶子节点来放各个点。pos决定初始位置,在二叉树中寻找叶子节点即可,如果pos没有空余的位置了就向后放(右子树)。起初我怀疑过这种方法,比如:
考虑从后往前输入,第一个例子:
0 0 69 0
0 33 69 0
0 33 69 51
77 33 69 51
但是第二个例子:
31492  0 0 0
31492 3890 0 0 
31492 3890 19243 0
31492 3890 19243 20523
这不是和结果不符吗?但还好可以进一步用pos和num的关系来决定位置,详见代码:
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=2e5+5;
int ans[maxn];
struct node{int l,r,num;int mid(){  return (l+r)/2; }
}tree[maxn<<2];
void build(int root,int low,int high){tree[root].l=low;tree[root].r=high;if(low==high){tree[root].num=1;return ;}int m=tree[root].mid();build(2*root,low,m);  //no if elsebuild(2*root+1,m+1,high);tree[root].num=tree[2*root].num+tree[2*root+1].num;
}
void insert(int root,int p,int val){if(tree[root].l==tree[root].r){//cout<<tree[root].l<<endl;tree[root].num=0;ans[tree[root].l]=val;return ;}if(p<=tree[2*root].num)insert(2*root,p,val);else  {p=p-tree[2*root].num;  //pos有一个作用:测试num,pos-num变成右子树的测试numinsert(2*root+1,p,val); //eg.p=3,left_num=1,for right_tree: p=2}  //if p=3,left_tree is full,left_num=0, find suitable place in right_tree.tree[root].num=tree[2*root].num+tree[2*root+1].num;
}
struct tnode{int pos,val;
}tp[maxn];
int main()
{//freopen("cin.txt","r",stdin);int n;while(cin>>n){build(1,1,n);for(int i=0;i<n;i++){scanf("%d%d",&tp[i].pos,&tp[i].val);}//for(int i=7;i>=1;i--)cout<<tree[i].num<<" ";  cout<<endl;for(int i=n-1;i>=0;i--){insert(1,tp[i].pos+1,tp[i].val);}//for(int i=7;i>=1;i--)cout<<tree[i].num<<" ";  cout<<endl;for(int i=1;i<n;i++){printf("%d ",ans[i]);}printf("%d\n",ans[n]);}return 0;
}

这篇关于poj 2828 Buy Tickets(动态队列·线段树单点更新)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/853786

相关文章

Android 悬浮窗开发示例((动态权限请求 | 前台服务和通知 | 悬浮窗创建 )

《Android悬浮窗开发示例((动态权限请求|前台服务和通知|悬浮窗创建)》本文介绍了Android悬浮窗的实现效果,包括动态权限请求、前台服务和通知的使用,悬浮窗权限需要动态申请并引导... 目录一、悬浮窗 动态权限请求1、动态请求权限2、悬浮窗权限说明3、检查动态权限4、申请动态权限5、权限设置完毕后

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque

Java使用POI-TL和JFreeChart动态生成Word报告

《Java使用POI-TL和JFreeChart动态生成Word报告》本文介绍了使用POI-TL和JFreeChart生成包含动态数据和图表的Word报告的方法,并分享了实际开发中的踩坑经验,通过代码... 目录前言一、需求背景二、方案分析三、 POI-TL + JFreeChart 实现3.1 Maven

Java导出Excel动态表头的示例详解

《Java导出Excel动态表头的示例详解》这篇文章主要为大家详细介绍了Java导出Excel动态表头的相关知识,文中的示例代码简洁易懂,具有一定的借鉴价值,有需要的小伙伴可以了解下... 目录前言一、效果展示二、代码实现1.固定头实体类2.动态头实现3.导出动态头前言本文只记录大致思路以及做法,代码不进

解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)

《解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)》该文章介绍了使用Redis的阻塞队列和Stream流的消息队列来优化秒杀系统的方案,通过将秒杀流程拆分为两条流水线,使用Redi... 目录Redis秒杀优化方案(阻塞队列+Stream流的消息队列)什么是消息队列?消费者组的工作方式每

vue基于ElementUI动态设置表格高度的3种方法

《vue基于ElementUI动态设置表格高度的3种方法》ElementUI+vue动态设置表格高度的几种方法,抛砖引玉,还有其它方法动态设置表格高度,大家可以开动脑筋... 方法一、css + js的形式这个方法需要在表格外层设置一个div,原理是将表格的高度设置成外层div的高度,所以外层的div需要

SpringBoot实现动态插拔的AOP的完整案例

《SpringBoot实现动态插拔的AOP的完整案例》在现代软件开发中,面向切面编程(AOP)是一种非常重要的技术,能够有效实现日志记录、安全控制、性能监控等横切关注点的分离,在传统的AOP实现中,切... 目录引言一、AOP 概述1.1 什么是 AOP1.2 AOP 的典型应用场景1.3 为什么需要动态插

Redis延迟队列的实现示例

《Redis延迟队列的实现示例》Redis延迟队列是一种使用Redis实现的消息队列,本文主要介绍了Redis延迟队列的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录一、什么是 Redis 延迟队列二、实现原理三、Java 代码示例四、注意事项五、使用 Redi

Redis缓存问题与缓存更新机制详解

《Redis缓存问题与缓存更新机制详解》本文主要介绍了缓存问题及其解决方案,包括缓存穿透、缓存击穿、缓存雪崩等问题的成因以及相应的预防和解决方法,同时,还详细探讨了缓存更新机制,包括不同情况下的缓存更... 目录一、缓存问题1.1 缓存穿透1.1.1 问题来源1.1.2 解决方案1.2 缓存击穿1.2.1

VUE动态绑定class类的三种常用方式及适用场景详解

《VUE动态绑定class类的三种常用方式及适用场景详解》文章介绍了在实际开发中动态绑定class的三种常见情况及其解决方案,包括根据不同的返回值渲染不同的class样式、给模块添加基础样式以及根据设... 目录前言1.动态选择class样式(对象添加:情景一)2.动态添加一个class样式(字符串添加:情