1. 問題引入從日常出行到算法模擬坐公交地鐵用優惠券或者免費換乘這是我們很多人每天都會遇到的場景。但你想過沒有如果讓你用程序來模擬這個過程你會怎么做這不僅僅是寫幾行代碼那么簡單它考驗的是你如何將現實世界中看似瑣碎的規則轉化為計算機能精確執行的邏輯。這正是CSP-J2019普及組第二題“公交換乘”的核心魅力所在。這道題源自《信息學奧賽一本通》的1983號題目同時也是洛谷 P5661。它沒有復雜的圖論或動態規劃就是一個純粹的“模擬題”。但千萬別小看“模擬”它往往是區分選手基本功是否扎實的關鍵。題目要求你根據給定的公交和地鐵乘坐記錄結合“優惠換乘”規則計算出實際的總花費。規則聽起來簡單坐地鐵后45分鐘內坐公交如果公交票價不超過地鐵票價就可以免費。但魔鬼藏在細節里——如何高效地管理45分鐘的時間窗口如何處理可能“過期”的優惠憑證如何確保每次消費都優先使用最“老”的優惠這些細節正是模擬題的坑點所在。很多初學者一看到題目描述覺得思路清晰上手就寫結果要么超時要么答案錯誤調試起來一頭霧水。這道題就是一個典型的“思路簡單實現易錯”的案例。它考察的不僅僅是編程語法更是嚴謹的邏輯思維、對數據結構的靈活運用以及邊界情況的處理能力。接下來我們就一起拆解這道題看看如何從零開始構建一個既高效又正確的解決方案。2. 規則拆解與核心矛盾分析在動手寫代碼之前我們必須像法官審閱法條一樣把題目規則逐字逐句吃透并找出其中隱含的“矛盾”或“陷阱”。2.1 規則原文精讀題目規則可以提煉為以下幾點消費類型每次出行記錄包含三個信息type0代表地鐵1代表公交、price票價、time從當天0點開始經過的分鐘數。地鐵規則乘坐地鐵時必須直接支付全款票價。同時這次乘坐會產生一張優惠憑證。這張憑證包含兩個關鍵屬性獲得時間即本次乘地鐵的time和面值即本次地鐵的price。公交規則乘坐公交時首先嘗試使用“優惠券”免費乘坐。使用優惠券的條件非常嚴格時間條件當前公交的乘車時間bus_time必須在某張優惠券的獲得時間coupon_time之后的45分鐘之內即bus_time - coupon_time 45。金額條件當前公交的票價bus_price必須不超過該優惠券的面值coupon_value即bus_price coupon_value。使用原則如果有多張符合條件的優惠券必須優先使用獲得時間最早的那一張。消耗性每張優惠券一旦被使用立即作廢。失敗處理如果找不到任何一張滿足上述時間和金額條件的優惠券那么本次公交乘坐就需要直接支付全款票價。2.2 核心矛盾與算法選擇理解規則后我們立刻能發現幾個需要程序解決的矛盾查找與匹配每次坐公交都需要從一堆“活著的”優惠券中找到那張“最早獲得”且“時間未超時”、“金額夠用”的券。這是一個典型的條件篩選排序問題。動態失效優惠券的有效期是動態的。隨著時間推進一些較早的券會“過期”超過45分鐘。我們需要一種機制來及時清理這些無效券避免對后續查找造成干擾。高效性題目數據規模是n 10^5。如果我們每次坐公交都遍歷所有歷史優惠券最壞情況O(n^2)在10^5的數據量下極有可能超時Time Limit Exceeded。因此算法效率是必須考慮的重點。基于以上分析一個高效的解決方案需要做到用一種數據結構來存儲所有“未使用且未過期”的優惠券。該數據結構要能支持我們快速找到“獲得時間最早”的券。要能方便地移除已經使用或過期的券。這自然讓我們聯想到隊列Queue的概念。隊列“先進先出”的特性正好符合“優先使用最早獲得的券”的規則。我們可以維護一個“優惠券隊列”。但普通的隊列無法處理“金額條件”和“動態過期”問題因此我們需要一個更靈活的“容器”。3. 數據結構設計與算法思路詳解直接使用標準隊列行不通因為公交消費時我們可能“跳過”隊頭那張金額不足的券去使用后面一張金額足夠的券嗎規則明確禁止這樣做必須優先使用最早獲得的、且符合條件的券。如果最早的這張券因為金額不足而不能用那么這次公交消費就不能使用任何優惠券即使后面有券符合條件必須付錢。這個規則決定了我們算法的核心流程對于每次公交消費我們從最早的優惠券開始依次檢查直到找到第一張同時滿足時間和金額條件的券。如果找到就用掉它將其從容器中刪除如果檢查過程中發現某張券已過期或者所有券都檢查完了也沒找到合適的那么本次公交就需要付費。3.1 數據結構數組模擬隊列 雙指針這是本題最經典和高效的做法。我們并不需要真的動態刪除數組中間的元素那樣效率低而是用數組配合兩個指針來模擬一個“滑動窗口”。coupon_time[i],coupon_value[i]: 用兩個數組分別存儲第i張優惠券的獲得時間和面值。數組大小開到n最多10^5即可。head: 隊頭指針指向當前待檢查的最早的優惠券索引。tail: 隊尾指針指向下一個優惠券可以存放的位置索引也就是當前隊列的長度。初始時head 0,tail 0。used[i]: 一個布爾數組標記第i張優惠券是否已被使用。這是關鍵因為我們可能跳過一些券金額不足但它們還在“隊列”中我們需要標記它已失效后續檢查時快速跳過。這個結構就像一個“傳送帶”。tail是入口每坐一次地鐵就生產一張新券放在tail位置然后tail。head是檢查的起點。檢查時我們從head開始向后掃描。3.2 算法流程分步拆解讓我們結合一次具體的公交消費走一遍流程初始化總花費total_cost 0。head 0,tail 0。讀入一條記錄(type,price,time)。如果是地鐵(type 0)總花費直接加上price。生產一張優惠券coupon_time[tail] time; coupon_value[tail] price; used[tail] false;tail。如果是公交(type 1)設置一個標志got_free false表示本次是否成功使用優惠券。清理隊頭過期或已使用的券這是一個非常重要的優化步驟。我們用while循環檢查head tail隊列不空且滿足以下兩個條件之一used[head] true券已使用time - coupon_time[head] 45券已過期 只要滿足就將head。這個操作確保了head指針始終指向隊列中第一個“未被使用且未過期”的券。注意這個清理是在每次公交消費時都做的保證了隊列的有效性。順序查找可用券從當前的head開始向后遍歷索引i直到i tail。如果used[i] true跳過。否則檢查條件price coupon_value[i]。注意此時時間條件一定滿足因為我們在上一步已經清理了過期的券。如果條件滿足說明找到了可用的券標記used[i] true設置got_free true并立即break跳出查找循環。這里必須跳出因為規則是使用第一張符合條件的券。結算如果got_free false沒找到券則總花費加上price。3.3 為什么這個算法是高效的關鍵在于head指針的單調遞增和每次公交消費時的“清理”操作。每張優惠券最多被head指針“路過”一次當它過期或被使用時head會越過它。每次公交消費的查找過程雖然看起來是遍歷但起始點head在不斷前進且查找范圍是當前所有“存活”的券。整體上所有優惠券被掃描的總次數與總記錄數n成線性關系。因此算法的時間復雜度是O(n)空間復雜度也是O(n)完全可以應對10^5的數據量。注意有些初學者會想用queuepairint, int這樣的STL隊列然后在公交消費時不斷彈出隊頭檢查不合適的再塞回去。這不僅是錯誤的違反了“必須使用最早一張符合條件的券”的規則因為你把不能用的塞回去它就不是最早的了而且效率低下。我們的“數組雙指針used標記”方法才是正解。4. 代碼實現與逐行解析C版本理解了算法我們來看具體的C實現。我會在關鍵代碼處加上詳細注釋。#include iostream using namespace std; const int MAXN 100005; // 根據數據范圍定義常量 int main() { int n; cin n; int coupon_time[MAXN]; // 存儲優惠券獲得時間 int coupon_value[MAXN]; // 存儲優惠券面值 bool used[MAXN] {false}; // 標記優惠券是否已使用初始化為false int head 0, tail 0; // 隊列頭尾指針 long long total_cost 0; // 總花費注意用long long防止溢出 for (int i 0; i n; i) { int type, price, time; cin type price time; if (type 0) { // 乘坐地鐵 // 乘坐地鐵必須付錢 total_cost price; // 獲得一張優惠券放入隊列尾部 coupon_time[tail] time; coupon_value[tail] price; // used[tail] 默認是false新券未被使用 tail; // 隊尾后移 } else { // 乘坐公交 bool got_free false; // 本次是否免費標志 // 關鍵步驟1清理隊頭過期或已使用的優惠券 // 這個循環確保head指向第一個“未使用且未過期”的券 while (head tail) { if (used[head]) { // 如果券已使用head直接后移 head; } else if (time - coupon_time[head] 45) { // 如果券已過期時間差大于45head后移 // 注意這里是 45 不是 45。第45分鐘時仍然有效。 head; } else { // 遇到第一個既未使用也未過期的券停止清理 break; } } // 關鍵步驟2順序查找可用的優惠券 // 從當前的head開始向后查找 for (int j head; j tail; j) { if (used[j]) { // 跳過已使用的券 continue; } // 此時券j一定未過期因為過期券在清理步驟已被head越過 // 只需判斷金額條件 if (price coupon_value[j]) { // 找到符合條件的券 used[j] true; // 標記為已使用 got_free true; // 標記本次免費 break; // 必須跳出只用第一張符合條件的券 } // 如果金額不夠繼續檢查下一張券 // 注意這里不能移動head因為這張券金額不足仍然是“存活”的 // 它可能用于滿足后續金額更低的公交消費。 } // 關鍵步驟3根據查找結果結算 if (!got_free) { // 沒找到可用優惠券需要付錢 total_cost price; } // 如果got_free為true則什么也不做免費乘坐 } } cout total_cost endl; return 0; }代碼要點解析數據類型total_cost使用long long。雖然單次消費不超過10^6總次數n不超過10^5總花費最大可能是10^11遠超int的范圍約2e9。這是一個經典的陷阱必須用long long。時間判斷條件time - coupon_time[head] 45。這里用而不是意味著在第45分鐘時差值為45優惠券仍然有效。這是題目描述的隱含條件務必注意。清理循環的位置清理過期券的操作放在每次公交消費的最開始。這保證了我們后續查找的起點 (head) 始終是有效的。如果放在查找循環內部邏輯會變得復雜且容易出錯。查找循環中的break一旦找到符合條件的券立即break。這是規則“優先使用最早的一張”的直接體現。如果不break就會錯誤地使用后面更新的券。used數組的重要性它讓我們可以“跳過”那些金額不足的券而不需要物理刪除它們。這些券保留在數組中head指針也可能因為它們金額不足而暫時不移動。它們可能在未來的某次公交消費中如果那趟公交票價更低被使用。5. 常見錯誤與調試心得即便思路正確實現時也容易踩坑。下面是我在教授這道題和調試學生代碼時總結的幾個高頻錯誤點。5.1 錯誤誤用“彈出-再壓入”的隊列// 錯誤示范 queuepairint, int q; // pairtime, value if (type 0) { cost price; q.push({time, price}); } else { bool found false; queuepairint, int temp; while (!q.empty()) { auto [t, v] q.front(); q.pop(); if (time - t 45) continue; // 過期丟棄 if (price v) { found true; // 使用這張券 break; } else { temp.push({t, v}); // 金額不夠暫存到臨時隊列 } } // 把臨時隊列里的券和原隊列剩下的券合并回去...這里邏輯已經混亂 if (!found) cost price; }問題分析這種做法違背了“必須使用最早一張符合條件的券”的原則。當隊頭券金額不足時你把它拿出來放到臨時隊列那么隊頭就變成了下一張券。對于本次公交消費你實際上跳過了這張最早的券去檢查后面的券了。這是規則不允許的。正確的邏輯是如果最早的這張券金額不足那么本次消費就不能使用任何優惠即使后面有券金額足夠。5.2 錯誤head指針移動邏輯錯誤在查找循環中當遇到一張金額不足的券時有的同學會錯誤地將head移動到j1。// 查找循環內 if (price coupon_value[j]) { ... } else { head j 1; // 錯誤不能移動head }問題分析head指針的移動只應該由“清理”步驟驅動即券已使用或過期。一張金額不足的券它依然是一張有效的、未過期的券必須留在“隊列”中供后續消費查詢。如果移動了head就等于把它從候選池里移除了后續更低票價的公交就無法使用它導致錯誤。5.3 錯誤時間條件判斷不精確// 錯誤1使用 if (time - coupon_time[head] 45) head; // 錯誤第45分鐘應有效 // 錯誤2在查找循環內重復判斷時間 for (int j head; j tail; j) { if (time - coupon_time[j] 45) continue; // 冗余且低效 // ... }問題分析錯誤1屬于邊界條件處理不當。錯誤2則反映了對算法結構理解不深。既然在公交消費開始時我們已經用while循環將head移動到了第一個未過期的券那么從head到tail-1的所有券在時間上都是有效的因為如果有過期的head會越過它。所以在查找循環內不需要再判斷時間只需判斷used和金額即可。重復判斷是多余的影響效率也增加出錯概率。5.4 調試技巧當你的程序輸出錯誤時可以嘗試以下方法構造小數據自己設計一些簡單的測試用例特別是邊界情況。例1一張地鐵券緊接著一張票價更高的公交應付費。例2一張地鐵券第44分鐘坐公交應免費第46分鐘再坐同票價公交應付費。例3多張地鐵券公交票價比其中一些高比另一些低。打印中間狀態在每次消費后打印head,tail,used數組的部分內容以及total_cost人工模擬核對。對比暴力算法寫一個最簡單的雙重循環暴力算法對于每次公交遍歷所有歷史地鐵記錄。用隨機生成的小規模數據n100運行兩個程序對比結果。這是驗證優化算法正確性的黃金標準。6. 舉一反三模擬類題目的通用解題框架“公交換乘”這道題是模擬題的優秀范例。通過它我們可以總結出解決此類問題的一般性思路。6.1 模擬題四步法精細化建模將題目描述的自然語言規則轉化為一條條無歧義的、可執行的邏輯判斷語句。像我們之前做的那樣列出所有“如果...那么...”的規則。這是最重要的一步決定了你程序邏輯的骨架。識別核心操作與數據結構分析規則中反復出現的操作。本題核心是“按時間順序存儲憑證”和“查找最早符合條件的憑證”。這提示我們需要一個能維護順序、支持高效查找/刪除的數據結構。數組模擬隊列、鏈表、甚至優先隊列都是備選需要根據具體規則選擇最合適的。設計算法流程用偽代碼勾勒出主循環。明確每一步先做什么后做什么。特別注意處理“狀態更新”的時機。例如本題清理過期券的操作放在每次公交消費開始時而不是結束時或另外的線程里。處理邊界與效率邊界時間、索引的邊界如45分鐘是還是、數據類型的范圍int還是long long、容器為空或滿的情況。效率分析數據規模估算最壞時間復雜度。如果可能超時思考如何優化核心操作如將O(n)查找優化為O(log n)或O(1)。本題通過維護head指針和used標記將整體復雜度優化到了O(n)。6.2 類似題目推薦掌握本題后可以嘗試以下洛谷上的同類模擬題鞏固技能P1540 [NOIP2010 提高組] 機器翻譯同樣需要維護一個定長的“隊列”來模擬內存處理“查找”和“替換”邏輯。P2058 [NOIP2016 普及組] 海港維護一個隨時間滑動的窗口統計窗口內不同國家的人數需要處理時間的推進和人員的離開。P7071 [CSP-J2020] 優秀的拆分雖然不涉及隊列但也是經典的按規則模擬考察二進制表示和嚴謹的邏輯。模擬題就像搭積木規則就是說明書。你的任務不是發明新算法而是成為一名忠實且高效的“規則執行者”。耐心、細心和對數據結構的敏感度是解好模擬題的關鍵。這道“公交換乘”題正是鍛煉這些能力的絕佳起點。下次當你再看到復雜的規則描述時希望你能像今天一樣冷靜地拆解、建模然后寫出優雅高效的代碼。