Posted on 2011-03-26 11:24
Onway 阅读(415)
评论(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都不会用。
传说中的线段树又是什么呢？