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