Onway

我是一只菜菜菜菜鸟...
posts - 61, comments - 56, trackbacks - 0, articles - 34

pku3038 贪心加优先队列

Posted on 2011-03-26 11:24 Onway 阅读(412) 评论(0)  编辑 收藏 引用 所属分类: 伤不起的ACM
题意:一辆公车从第1个站开到第n个站,再开回第1个站。车上人数容量为c。有K组数,每组数给出num个人要从s站坐到e站。问公车最多能让几个人到达目的站。
思路:用一个数组down[]记录每个站要下车的人数,用一个优先队列记录车上的人的终点站(用作踢人)。枚举从第1个站到最后一个站,先进行下车过程,再进行上车,注意上车时候可能要踢人。
贪心原则:
1)车厢容量要得到最好的利用。
2)优先选择路程短的乘客。

解题步骤:
1)输入的时候,将公车线路转换为一条直线。输入注意起点站大于终点站的,为了满足第二条原则,都让他们在回程的时候上车。
2)为了满足第一条原则,当然要让起点站最先的人先上。要排序。
3)每个站都停一次,判断有没有人要上车和下车。先进行下车过程。上车过程有很多分支判断,要注意考虑周全。

后记:
在练习赛里见到这个题目,有点象校现场赛的一题,但多了一个容量限制。所以当时也没多想,放弃了。
后来讨论后发现这个题目感觉自己有能力做。感觉要用到优先队列,所以一直拖到二叉堆的模板完成,期间最有成就感的是使用了回调函数。
写的过程一直很相信自己的思路,只使用了一个优先队列来进行上车和下车两个过程。但由于太多自信,修修补补两百行多的代码终于经过五个小时的调试由WA变成了TLE。期间最大的收获是发现对题意的理解出了一点偏差。
第二天重写了一个70行的代码,还是WA,又经过一个多小时的调试,发现了一个很弱智的错误。尝试用getback()从最小堆里取得最大元素。
这时马上否定了自信加坚持了多个小时的思路,只用一个队列进行上下车两个过程。在STL里随便找了一会,也没发现有满足要求的数据结构。
然后尝试用两个优先队列。由于思维被第一次的代码疆住了,感觉两个队列之间很难进行同步。
然后开始考虑洪爷说的枚举每一个站。然后莫名就想到了以上的思路,只有一个优先队列记录被踢的。然后又漏了一个变量的维护。

在接近十个小时的调试中,vim最多的时候开了四个窗口,但不会调大小。gdb的调试窗口和条件断点又忘了。
STL的map和set,还有priority_queue都不会用。
传说中的线段树又是什么呢?



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