风雪梦

柳絮因风起

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  4 Posts :: 76 Stories :: 3 Comments :: 0 Trackbacks

常用链接

留言簿

我参与的团队

搜索

  •  

最新评论

  • 1. re: LightOJ1080 Binary Simulation
  • 话说加个PushDown操作不就OK了咩?
  • --仗剑奔走天涯
  • 2. re: 正式开博
  • 加油!
  • --leafcloudsky
  • 3. re: 启航杯啊
  • 太屎了!!我竟然就这么的WA了两次,最终发现,第四题少了两句初始化,第五题把数组开错地方了,算法没问题,结果就这么从四题跌到二题,太伤不起了!!可怜我调spfa调了一晚上!!尼玛啊!!
  • --浅雨歌

阅读排行榜

评论排行榜

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

题目一看好高深啊疑问,不过还好,AC。。

这道题如果正着看,那么每一个人的地方都有可能变动,但是如果倒着看,每一个只要入队了,他的位置就不再改变,这样的话就是一道赤裸裸的线段树单点更新了,每一个结点存储的是该区间内还有多少个空位,每一次遇到一个人的时候,都把他插入到正确的位置,至于怎么算正确的位置,如果当前结点左子树权值大于pos,那么就往左边放,否则就往右边放,放不进去左边的时候,pos要减去左边的空位数,否则的话有可能右边也放不进去,最后根本放不到叶子结点里面。每进入一个区间,该区间的空位数就减少一个,这个千万不要忘了处理。最后用一个数组来存储插入进去以后的最终位置。

view code

posted on 2013-01-11 00:55 浅雨歌 阅读(82) 评论(0)  编辑 收藏 引用 所属分类: 线段树

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理