這題我印象太深了。UVa 145 Gondwanaland Telecom老OJ題庫里非常經(jīng)典的一道電話計費模擬題。題目虛構(gòu)了一個叫岡瓦那蘭的電信網(wǎng)絡(luò)給你一張固定費率表要求把所有通話按三個時段的分鐘數(shù)拆開再算出每一單的最終費用。第一次做到這題的人十有八九會被“一天切成三段費率”“跨天通話算到哪一天”“金額為什么總要差0.01”這幾個問題繞進(jìn)去。我當(dāng)年在訓(xùn)練賽里也栽過兩回后來把整套思路順清楚之后才發(fā)現(xiàn)這題根本不是算法難而是建模和邊界處理有沒有做到位。今天把這題的完整思路、可運行代碼和WA教訓(xùn)一次性整理出來給正在刷模擬題的朋友做個參考。1. 題目背景與計費規(guī)則全解析1.1 什么叫 Gondwanaland TelecomGondwanaland 這個名字取自地質(zhì)史上的岡瓦納古大陸題目借來當(dāng)一個虛構(gòu)國家名。場景很直白這個國家有一套長途電話計費系統(tǒng)不同國家使用不同費率檔位同一天內(nèi)不同時間段價格也不一樣。你要寫一個程序讀入若干條通話記錄計算并輸出每條記錄的費用。這種“模擬現(xiàn)實業(yè)務(wù)規(guī)則”的題目在競賽里定位很明確不考復(fù)雜算法考的是你能不能把帶邊界、帶隱含條件的規(guī)則不重不漏地翻譯成代碼。很多人覺得模擬題簡單寫起來才發(fā)現(xiàn)什么叫“樣例過了隱藏數(shù)據(jù)瘋狂WA”。主要原因就是現(xiàn)實規(guī)則里的細(xì)節(jié)太多一個邊界沒對上整個計費結(jié)果就偏了。1.2 四類國家與三個時段的費率表題目給了一張固定費率表不需要從輸入讀取。標(biāo)準(zhǔn)表大概是這樣的費率類別Day 08:00-18:00Evening 18:00-22:00Night 22:00-08:00A0.100.060.02B0.250.150.05C0.530.330.13D0.870.470.17注意這里的單位是美元/分鐘不是美分/分鐘。A類國家白天每分鐘0.10美元晚上0.06美元夜間0.02美元。三個時段拼起來正好完整覆蓋一天24小時沒有重疊也沒有缺口。我建議拿到這張表之后第一時間把它換算成美分存進(jìn)數(shù)組。A類對應(yīng){10, 6, 2}B類對應(yīng){25, 15, 5}這樣計算全用整數(shù)后面浮點誤差的坑直接繞開。1.3 輸入記錄里藏著哪些信息每條通話記錄是一行常見格式如下C 1111111 2222222 03/15 20:30 120字段拆開看C被叫方所在國家對應(yīng)的費率類別查表用的索引。1111111主叫號碼。2222222被叫號碼。03/15通話開始日期月/日。20:30通話開始時間24小時制。120通話持續(xù)分鐘數(shù)。輸入以單獨一個#字符結(jié)束。很多版本會注明每次通話最長不超過800分鐘這個限制非常關(guān)鍵意味著哪怕你用最暴力的逐分鐘模擬數(shù)據(jù)量也完全撐得住。輸出通常要求打印主叫號碼、被叫號碼、日期、開始時間、通話時長和費用費用精確到美分。不同OJ的復(fù)述版本在字段順序上可能有點差異但計費邏輯是完全一樣的。2. 從題意到模型如何把計費規(guī)則轉(zhuǎn)換成代碼2.1 把一天切成1440個離散分鐘時間格式對人類友好但計算機計算起來不方便。20:30沒法直接和480這種數(shù)字比大小所以第一步永遠(yuǎn)是把時間轉(zhuǎn)成“當(dāng)天第幾分鐘”。一天有24小時每小時60分鐘總共24 * 60 1440分鐘。我用從0開始的編號表示00:00對應(yīng)第0分鐘08:00對應(yīng)第8 * 60 480分鐘18:00對應(yīng)第18 * 60 1080分鐘22:00對應(yīng)第22 * 60 1320分鐘23:59對應(yīng)第1439分鐘。比如20:30就是20 * 60 30 1230。從20:30開始打120分鐘結(jié)束時間是1350也就是22:30。整個過程全部是整數(shù)加法非常干凈。2.2 用類型數(shù)組替代區(qū)間判斷計費的核心是“判斷某個分鐘屬于哪個時段”。如果你在計費循環(huán)里寫一堆if (m 480 m 1080)的判斷代碼會變丑而且特別容易在邊界上混。更穩(wěn)的做法是啟動時預(yù)先算好每個分鐘的類型放進(jìn)一個長度為1440的數(shù)組里。標(biāo)記規(guī)則480 ~ 1079屬于Day即08:00到18:001080 ~ 1319屬于Evening即18:00到22:001320 ~ 1439和0 ~ 479屬于Night即22:00到次日08:00。這樣在計費循環(huán)里只需要一行minuteType[cur]就能拿到當(dāng)前分鐘對應(yīng)的費率下標(biāo)。把“區(qū)間歸屬”這種反復(fù)使用的邏輯做成一次預(yù)處理查表是模擬題里性價比最高的建模方式。2.3 為什么我用整數(shù)美分計費費率是兩位小數(shù)比如0.10、0.06。如果直接寫成ans rate * dur; // rate是doubledouble類型在累加幾百次之后可能變成一個接近但不等于理論值的數(shù)。比如實際結(jié)果是5.40double里存的是5.399999999。最終printf四舍五入時可能還是5.40也可能變成5.39。OJ最喜歡這種隱蔽的精度差WA了你都查不出原因。正確的做法是統(tǒng)一用整數(shù)美分費率類別DayEveningNightA1062B25155C533313D874717每次累加的是整數(shù)美分最后輸出美元時用totalCents / 100取整數(shù)部分用totalCents % 100取小數(shù)部分。這樣整個計算過程不出現(xiàn)浮點數(shù)精度問題直接從根上消失。3. 代碼實現(xiàn)一份可以直接跑通的方案3.1 時間表的預(yù)處理我先把分鐘類型數(shù)組建好。三個分界點是480、1080、1320分別對應(yīng)08:00、18:00、22:00。注意這里我采用的是“左閉右開”的區(qū)間歸屬每個整點時刻歸入后一個時段。比如18:00整歸Evening而不是歸Day。#include bits/stdc.h using namespace std; // 四類費率單位是美分/分鐘 const int PRICE[4][3] { {10, 6, 2}, // A {25, 15, 5}, // B {53, 33, 13}, // C {87, 47, 17} // D }; int minuteType[1440]; void initMinuteType() { for (int i 0; i 1440; i) { if (i 480 i 1080) minuteType[i] 0; // Day else if (i 1080 i 1320) minuteType[i] 1; // Evening else minuteType[i] 2; // Night } }這段預(yù)處理是最容易出錯的地方。如果你把i 480寫成i 480那08:00這一分鐘就會被算進(jìn)Night所有從08:00整開始的通話都會少一分鐘Day費率。3.2 輸入解析的終止條件輸入最后一行是單獨的#用cin c讀取第一個字符判斷即可。因為每條記錄都是空格分隔的固定字段直接用流讀取最省事。如果擔(dān)心有空行干擾也可以用getline按行讀再丟進(jìn)stringstream但本題標(biāo)準(zhǔn)輸入下cin完全夠用。int main() { initMinuteType(); char c; while (cin c) { if (c #) break; string caller, callee; int month, day, hh, mm, duration; cin caller callee month day hh mm duration; int start hh * 60 mm; long long totalCents 0; // 逐分鐘模擬計費 for (int t 0; t duration; t) { int cur (start t) % 1440; // 跨天自動回到當(dāng)天0點 totalCents PRICE[c - A][minuteType[cur]]; } printf(%s %s %02d/%02d %02d:%02d %d %lld.%02lld\n, caller.c_str(), callee.c_str(), month, day, hh, mm, duration, totalCents / 100, totalCents % 100); } return 0; }3.3 計費主循環(huán)與跨天處理重點看循環(huán)里的兩行int cur (start t) % 1440; totalCents PRICE[c - A][minuteType[cur]];start t是從通話開始數(shù)起的第t分鐘。假設(shè)開始時間是23:30start 1410打到第60分鐘時1460已經(jīng)超過1439。這時對1440取模得到20對應(yīng)次日00:20。這樣跨天通話自動正確歸屬到Night區(qū)間。費率索引PRICE[c - A]通過c - A把字符A、B、C、D轉(zhuǎn)成0到3的下標(biāo)和費率表的行對應(yīng)。minuteType[cur]則是當(dāng)前分鐘屬于0、1、2哪個時段。兩個下標(biāo)一組合取到的就是正確的每分鐘費率。3.4 輸出費用的格式控制printf里我用了%lld.%02lld%02lld保證小數(shù)部分是兩位比如5.50不會變成5.5。日期和時間也用了%02d保證前導(dǎo)零。有些朋友習(xí)慣算完就轉(zhuǎn)成double再printf(%.2f, totalCents / 100.0)。這在小數(shù)據(jù)量上看不出問題但既然已經(jīng)用整數(shù)算出了精確結(jié)果最后這一步?jīng)]必要再把精度交給浮點數(shù)直接用整數(shù)格式化最安全。寫模擬題時輸出格式一定要對著樣例逐字符檢查少個空格、多一位零都是WA。4. 實戰(zhàn)避坑我用這道題換來的WA教訓(xùn)4.1 邊界時間歸屬08:00整到底算白天還是夜間這是這道題最經(jīng)典的坑。三個時段邊界是08:00、18:00、22:00。如果題目描述只說“from 08:00 to 18:00”沒有明確開閉區(qū)間你需要自己定一套一致的標(biāo)準(zhǔn)。按大多數(shù)題解和實際題意的處理方式08:00整算Day不是Night18:00整算Evening不是Day22:00整算Night不是Evening。在分鐘數(shù)組里的直接體現(xiàn)就是480、1080、1320這三個點都?xì)w入后一個區(qū)間。如果你把條件寫成i 480那08:00這一分鐘就會算到Night每通跨08:00整的電話都會差一分鐘費率。我一開始寫錯成i 480 i 1080結(jié)果手動測試時挑的樣例都避開了邊界上OJ直接WA。后來把費率表和時間軸畫在紙上才發(fā)現(xiàn)08:00那分鐘的歸屬出了問題。4.2 跨天通話忘記取?？缣焓堑诙€高發(fā)坑。有人想得比較直接開始時間23:30通話時長80分鐘那就從第1410分鐘一直加到第1490分鐘。結(jié)果數(shù)組下標(biāo)越界或者拿1490去和480、1080、1320比較整個時段判斷全亂。當(dāng)年我的錯誤是把“跨天”理解成“日期1”還專門寫了個day的邏輯。其實題目里日期只是展示用真正決定費率的是小時和分鐘。逐分鐘模擬時一個% 1440就解決所有跨天問題。如果你選擇用區(qū)間切分法而不是逐分鐘模擬也要注意任何邊界比較之前先把當(dāng)前分鐘對1440取模。絕不能用超過1439的分鐘數(shù)直接參與時段判斷。4.3 浮點誤差與四舍五入有一類WA特別隱蔽邏輯全對費率表也查對了輸出就差一分錢。原因十有八九是用了浮點累計。比如B類費率0.15累計100分鐘理論上是15.00美元但double累加可能得到14.999999。再對輸出做四舍五入結(jié)果變成14.99。這種錯誤在本地測試時幾乎復(fù)現(xiàn)不出來因為個別樣例誤差方向可能正好抵消。但OJ的數(shù)據(jù)量大誤差累積到一定程度就爆了。我的原則很簡單凡是涉及價格、金額、費率能轉(zhuǎn)成整數(shù)就轉(zhuǎn)整數(shù)。美分就是實際上最合適的統(tǒng)一單位。第一步把美元費率乘以100第二步全程整數(shù)加減法第三步輸出時分別取整除商和余數(shù)。這樣提交結(jié)果完全可復(fù)現(xiàn)不存在浮點誤差。4.4 常見問題速查表癥狀可能原因處理方法輸出金額差0.01double累加誤差改用整數(shù)美分計算時段首尾判斷錯誤邊界歸屬不統(tǒng)一把480、1080、1320歸入后一區(qū)間跨天通話結(jié)果錯結(jié)束分鐘沒取模逐分鐘模擬用%1440輸出多空或少空格字段順序/日期格式不對逐字符對照樣例輸出讀取到#后多跑一次終止條件判斷位置錯誤cin c后先判斷再繼續(xù)讀大樣例金額溢出intint范圍不夠用long long存總美分第6條我多說一句總費用看起來只有幾十美元但中間如果累加的是美分幾十美元對應(yīng)幾千美分int也夠。但如果你把單分鐘費率放大、數(shù)據(jù)量變大或者以后做變種題int就可能不夠。題解代碼里我直接用long long養(yǎng)成習(xí)慣不丟人。4.5 一個調(diào)試技巧如果WA了但找不到錯建議把費率表、當(dāng)天分鐘數(shù)組、每條通話的分段區(qū)間全部打印出來。比如輸入C 1111111 2222222 03/15 20:30 120手算一遍費率20:30對應(yīng)第1230分鐘22:00對應(yīng)第1320分鐘。前90分鐘是Evening費率33美分后30分鐘是Night費率13美分?？傎M用等于90 * 33 30 * 13 2970 390 3360美分即33.60美元。把這個數(shù)和你程序的輸出對比如果不一樣就知道是區(qū)間拆分錯了還是費率查錯了。比起看半天代碼這種定位方式快得多。5. 進(jìn)一步優(yōu)化如果數(shù)據(jù)范圍變大怎么辦5.1 用區(qū)間合并代替逐分鐘枚舉逐分鐘模擬能過這題靠的是題目給的時長上限。但想一想如果同樣的規(guī)則通話時長變成10^9分鐘記錄數(shù)變成10^5逐分鐘算法肯定直接超時。這時候需要用“區(qū)間切分”的思路。核心邏輯是一次通話會被若干時間邊界切成連續(xù)子區(qū)間每個子區(qū)間內(nèi)部費率相同。我們不需要逐分鐘走只需要找到所有的費率切換點然后把每個區(qū)間的長度直接乘以費率。以當(dāng)前分鐘為起點找下一個切換點如果當(dāng)前屬于Day下一個切換點是18:00如果當(dāng)前屬于Evening下一個切換點是22:00如果當(dāng)前屬于Night下一個切換點是次日08:00。每段累加完畢把當(dāng)前指針切到下一個點直到超過通話結(jié)束時間。5.2 快速切分法代碼示意下面這段代碼展示“按段切分”的寫法思路比逐分鐘多繞一點但很有代表性int getType(int minute) { minute % 1440; if (minute 480 minute 1080) return 0; if (minute 1080 minute 1320) return 1; return 2; } long long billBySegments(int start, int duration, const int rateArr[3]) { int cur start; int end start duration; long long totalCents 0; while (cur end) { int nowType getType(cur); int curMod cur % 1440; int cutTime; // 找下一個費率切換點但不超過end if (nowType 0) { cutTime min(end, cur (1080 - curMod)); // 到18:00 } else if (nowType 1) { cutTime min(end, cur (1320 - curMod)); // 到22:00 } else { if (curMod 480) { cutTime min(end, cur (480 - curMod)); // 到08:00 } else { cutTime min(end, cur (1440 - curMod 480)); // 跨天到08:00 } } totalCents 1LL * (cutTime - cur) * rateArr[nowType]; cur cutTime; } return totalCents; }這段代碼里最需要注意的就是Night區(qū)間的跨天分支。如果curMod是比如23:30也就是1410下一個切換點在次日08:00距離就是1440 - 1410 480 510分鐘。這個算法在邏輯上比逐分鐘復(fù)雜但運行時復(fù)雜度從“通話時長”降到了“最多跨4個時段”也就是常數(shù)級別。我平時刷題遇到這種“暴力能過但可以優(yōu)化”的題也會順手把優(yōu)化版想一遍。不是為了炫技而是為了在考場上遇到變種題時心里有底。5.3 從模擬題到真實話單系統(tǒng)的聯(lián)想這道題雖然叫“Gondwanaland Telecom”但背后的計費模型很多現(xiàn)實場景都在用。停車收費、階梯電價、云資源按量計費本質(zhì)上都是“在時間軸上按區(qū)間分段每段套不同單價”。之前有朋友去通信行業(yè)面試被問到“跨月通話怎么計費”其實思路和這題的跨天處理一模一樣通話時長拆成兩段前一段歸上個月后一段歸下個月邊界落在月結(jié)日零點。date的月份進(jìn)位和這里的%1440取模本質(zhì)都是處理“跨邊界”。模擬題練出來的不是算法難度而是把模糊規(guī)則清晰編碼的工程能力這一點在工作中比單純的算法技巧更有價值。我個人做這題最大的收獲是養(yǎng)成了一個習(xí)慣凡是遇到計費、日期、時段相關(guān)題目先拿一張紙畫出0到1440的時間軸把8:00、18:00、22:00三個點標(biāo)在軸上再決定區(qū)間歸屬。這個動作看著多花兩分鐘實際上能省下好幾次WA的排查時間。如果你也卡在這題上別急著懷疑算法想復(fù)雜了大概率就是邊界和精度的問題。把時間軸畫清楚把金額換成整數(shù)再跑一遍很多問題自己就現(xiàn)形了。