这题我印象太深了。UVa 145 Gondwanaland Telecom老OJ题库里非常经典的一道电话计费模拟题。题目虚构了一个叫冈瓦那兰的电信网络给你一张固定费率表要求把所有通话按三个时段的分钟数拆开再算出每一单的最终费用。第一次做到这题的人十有八九会被“一天切成三段费率”“跨天通话算到哪一天”“金额为什么总要差0.01”这几个问题绕进去。我当年在训练赛里也栽过两回后来把整套思路顺清楚之后才发现这题根本不是算法难而是建模和边界处理有没有做到位。今天把这题的完整思路、可运行代码和WA教训一次性整理出来给正在刷模拟题的朋友做个参考。1. 题目背景与计费规则全解析1.1 什么叫 Gondwanaland TelecomGondwanaland 这个名字取自地质史上的冈瓦纳古大陆题目借来当一个虚构国家名。场景很直白这个国家有一套长途电话计费系统不同国家使用不同费率档位同一天内不同时间段价格也不一样。你要写一个程序读入若干条通话记录计算并输出每条记录的费用。这种“模拟现实业务规则”的题目在竞赛里定位很明确不考复杂算法考的是你能不能把带边界、带隐含条件的规则不重不漏地翻译成代码。很多人觉得模拟题简单写起来才发现什么叫“样例过了隐藏数据疯狂WA”。主要原因就是现实规则里的细节太多一个边界没对上整个计费结果就偏了。1.2 四类国家与三个时段的费率表题目给了一张固定费率表不需要从输入读取。标准表大概是这样的费率类别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小时没有重叠也没有缺口。我建议拿到这张表之后第一时间把它换算成美分存进数组。A类对应{10, 6, 2}B类对应{25, 15, 5}这样计算全用整数后面浮点误差的坑直接绕开。1.3 输入记录里藏着哪些信息每条通话记录是一行常见格式如下C 1111111 2222222 03/15 20:30 120字段拆开看C被叫方所在国家对应的费率类别查表用的索引。1111111主叫号码。2222222被叫号码。03/15通话开始日期月/日。20:30通话开始时间24小时制。120通话持续分钟数。输入以单独一个#字符结束。很多版本会注明每次通话最长不超过800分钟这个限制非常关键意味着哪怕你用最暴力的逐分钟模拟数据量也完全撑得住。输出通常要求打印主叫号码、被叫号码、日期、开始时间、通话时长和费用费用精确到美分。不同OJ的复述版本在字段顺序上可能有点差异但计费逻辑是完全一样的。2. 从题意到模型如何把计费规则转换成代码2.1 把一天切成1440个离散分钟时间格式对人类友好但计算机计算起来不方便。20:30没法直接和480这种数字比大小所以第一步永远是把时间转成“当天第几分钟”。一天有24小时每小时60分钟总共24 * 60 1440分钟。我用从0开始的编号表示00:00对应第0分钟08:00对应第8 * 60 480分钟18:00对应第18 * 60 1080分钟22:00对应第22 * 60 1320分钟23:59对应第1439分钟。比如20:30就是20 * 60 30 1230。从20:30开始打120分钟结束时间是1350也就是22:30。整个过程全部是整数加法非常干净。2.2 用类型数组替代区间判断计费的核心是“判断某个分钟属于哪个时段”。如果你在计费循环里写一堆if (m 480 m 1080)的判断代码会变丑而且特别容易在边界上混。更稳的做法是启动时预先算好每个分钟的类型放进一个长度为1440的数组里。标记规则480 ~ 1079属于Day即08:00到18:001080 ~ 1319属于Evening即18:00到22:001320 ~ 1439和0 ~ 479属于Night即22:00到次日08:00。这样在计费循环里只需要一行minuteType[cur]就能拿到当前分钟对应的费率下标。把“区间归属”这种反复使用的逻辑做成一次预处理查表是模拟题里性价比最高的建模方式。2.3 为什么我用整数美分计费费率是两位小数比如0.10、0.06。如果直接写成ans rate * dur; // rate是doubledouble类型在累加几百次之后可能变成一个接近但不等于理论值的数。比如实际结果是5.40double里存的是5.399999999。最终printf四舍五入时可能还是5.40也可能变成5.39。OJ最喜欢这种隐蔽的精度差WA了你都查不出原因。正确的做法是统一用整数美分费率类别DayEveningNightA1062B25155C533313D874717每次累加的是整数美分最后输出美元时用totalCents / 100取整数部分用totalCents % 100取小数部分。这样整个计算过程不出现浮点数精度问题直接从根上消失。3. 代码实现一份可以直接跑通的方案3.1 时间表的预处理我先把分钟类型数组建好。三个分界点是480、1080、1320分别对应08:00、18:00、22:00。注意这里我采用的是“左闭右开”的区间归属每个整点时刻归入后一个时段。比如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 } }这段预处理是最容易出错的地方。如果你把i 480写成i 480那08:00这一分钟就会被算进Night所有从08:00整开始的通话都会少一分钟Day费率。3.2 输入解析的终止条件输入最后一行是单独的#用cin c读取第一个字符判断即可。因为每条记录都是空格分隔的固定字段直接用流读取最省事。如果担心有空行干扰也可以用getline按行读再丢进stringstream但本题标准输入下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; // 跨天自动回到当天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 计费主循环与跨天处理重点看循环里的两行int cur (start t) % 1440; totalCents PRICE[c - A][minuteType[cur]];start t是从通话开始数起的第t分钟。假设开始时间是23:30start 1410打到第60分钟时1460已经超过1439。这时对1440取模得到20对应次日00:20。这样跨天通话自动正确归属到Night区间。费率索引PRICE[c - A]通过c - A把字符A、B、C、D转成0到3的下标和费率表的行对应。minuteType[cur]则是当前分钟属于0、1、2哪个时段。两个下标一组合取到的就是正确的每分钟费率。3.4 输出费用的格式控制printf里我用了%lld.%02lld%02lld保证小数部分是两位比如5.50不会变成5.5。日期和时间也用了%02d保证前导零。有些朋友习惯算完就转成double再printf(%.2f, totalCents / 100.0)。这在小数据量上看不出问题但既然已经用整数算出了精确结果最后这一步没必要再把精度交给浮点数直接用整数格式化最安全。写模拟题时输出格式一定要对着样例逐字符检查少个空格、多一位零都是WA。4. 实战避坑我用这道题换来的WA教训4.1 边界时间归属08:00整到底算白天还是夜间这是这道题最经典的坑。三个时段边界是08:00、18:00、22:00。如果题目描述只说“from 08:00 to 18:00”没有明确开闭区间你需要自己定一套一致的标准。按大多数题解和实际题意的处理方式08:00整算Day不是Night18:00整算Evening不是Day22:00整算Night不是Evening。在分钟数组里的直接体现就是480、1080、1320这三个点都归入后一个区间。如果你把条件写成i 480那08:00这一分钟就会算到Night每通跨08:00整的电话都会差一分钟费率。我一开始写错成i 480 i 1080结果手动测试时挑的样例都避开了边界上OJ直接WA。后来把费率表和时间轴画在纸上才发现08:00那分钟的归属出了问题。4.2 跨天通话忘记取模跨天是第二个高发坑。有人想得比较直接开始时间23:30通话时长80分钟那就从第1410分钟一直加到第1490分钟。结果数组下标越界或者拿1490去和480、1080、1320比较整个时段判断全乱。当年我的错误是把“跨天”理解成“日期1”还专门写了个day的逻辑。其实题目里日期只是展示用真正决定费率的是小时和分钟。逐分钟模拟时一个% 1440就解决所有跨天问题。如果你选择用区间切分法而不是逐分钟模拟也要注意任何边界比较之前先把当前分钟对1440取模。绝不能用超过1439的分钟数直接参与时段判断。4.3 浮点误差与四舍五入有一类WA特别隐蔽逻辑全对费率表也查对了输出就差一分钱。原因十有八九是用了浮点累计。比如B类费率0.15累计100分钟理论上是15.00美元但double累加可能得到14.999999。再对输出做四舍五入结果变成14.99。这种错误在本地测试时几乎复现不出来因为个别样例误差方向可能正好抵消。但OJ的数据量大误差累积到一定程度就爆了。我的原则很简单凡是涉及价格、金额、费率能转成整数就转整数。美分就是实际上最合适的统一单位。第一步把美元费率乘以100第二步全程整数加减法第三步输出时分别取整除商和余数。这样提交结果完全可复现不存在浮点误差。4.4 常见问题速查表症状可能原因处理方法输出金额差0.01double累加误差改用整数美分计算时段首尾判断错误边界归属不统一把480、1080、1320归入后一区间跨天通话结果错结束分钟没取模逐分钟模拟用%1440输出多空或少空格字段顺序/日期格式不对逐字符对照样例输出读取到#后多跑一次终止条件判断位置错误cin c后先判断再继续读大样例金额溢出intint范围不够用long long存总美分第6条我多说一句总费用看起来只有几十美元但中间如果累加的是美分几十美元对应几千美分int也够。但如果你把单分钟费率放大、数据量变大或者以后做变种题int就可能不够。题解代码里我直接用long long养成习惯不丢人。4.5 一个调试技巧如果WA了但找不到错建议把费率表、当天分钟数组、每条通话的分段区间全部打印出来。比如输入C 1111111 2222222 03/15 20:30 120手算一遍费率20:30对应第1230分钟22:00对应第1320分钟。前90分钟是Evening费率33美分后30分钟是Night费率13美分。总费用等于90 * 33 30 * 13 2970 390 3360美分即33.60美元。把这个数和你程序的输出对比如果不一样就知道是区间拆分错了还是费率查错了。比起看半天代码这种定位方式快得多。5. 进一步优化如果数据范围变大怎么办5.1 用区间合并代替逐分钟枚举逐分钟模拟能过这题靠的是题目给的时长上限。但想一想如果同样的规则通话时长变成10^9分钟记录数变成10^5逐分钟算法肯定直接超时。这时候需要用“区间切分”的思路。核心逻辑是一次通话会被若干时间边界切成连续子区间每个子区间内部费率相同。我们不需要逐分钟走只需要找到所有的费率切换点然后把每个区间的长度直接乘以费率。以当前分钟为起点找下一个切换点如果当前属于Day下一个切换点是18:00如果当前属于Evening下一个切换点是22:00如果当前属于Night下一个切换点是次日08:00。每段累加完毕把当前指针切到下一个点直到超过通话结束时间。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区间的跨天分支。如果curMod是比如23:30也就是1410下一个切换点在次日08:00距离就是1440 - 1410 480 510分钟。这个算法在逻辑上比逐分钟复杂但运行时复杂度从“通话时长”降到了“最多跨4个时段”也就是常数级别。我平时刷题遇到这种“暴力能过但可以优化”的题也会顺手把优化版想一遍。不是为了炫技而是为了在考场上遇到变种题时心里有底。5.3 从模拟题到真实话单系统的联想这道题虽然叫“Gondwanaland Telecom”但背后的计费模型很多现实场景都在用。停车收费、阶梯电价、云资源按量计费本质上都是“在时间轴上按区间分段每段套不同单价”。之前有朋友去通信行业面试被问到“跨月通话怎么计费”其实思路和这题的跨天处理一模一样通话时长拆成两段前一段归上个月后一段归下个月边界落在月结日零点。date的月份进位和这里的%1440取模本质都是处理“跨边界”。模拟题练出来的不是算法难度而是把模糊规则清晰编码的工程能力这一点在工作中比单纯的算法技巧更有价值。我个人做这题最大的收获是养成了一个习惯凡是遇到计费、日期、时段相关题目先拿一张纸画出0到1440的时间轴把8:00、18:00、22:00三个点标在轴上再决定区间归属。这个动作看着多花两分钟实际上能省下好几次WA的排查时间。如果你也卡在这题上别急着怀疑算法想复杂了大概率就是边界和精度的问题。把时间轴画清楚把金额换成整数再跑一遍很多问题自己就现形了。