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