Posted on 2011-03-26 11:24
Onway 閱讀(432)
評論(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都不會用。
傳說中的線段樹又是什么呢？