第一次看到编号 145 的 Gondwanaland Telecom 这道老题时我心里想这不就是一个电话计费模拟题吗结果一连交了三次都是 WA最后发现坑全藏在输入格式和“跨天通话”里。后来把整道题的模型理顺之后才明白它为什么能成为很多人的入门噩梦。这道题核心并不难但信息密度非常大一张五档费率表、三段时间区间、一组区号前缀映射再给若干条通话记录让你把每一条的费用算出来。它适合刚学完 C 字符串处理和结构体的人拿来练手也适合想复习模拟题细节的老手。下面我把计费模型、前缀匹配、跨时段计算和实际踩坑经历一次性讲清楚。1. 看懂计费模型五档费率与三个时段1.1 固定的费率表才是真正的“规则书”题目里最容易被忽略的一点是费率不是呼叫方自己选的而是由被叫号码的区号前缀决定的。电话公司预先维护了一张表把不同的区号前缀映射到A-E五档费率中的某一档。每一档费率又分成三个时段每分钟价格固定。以我手上最常见的版本为例费率表长这样费率档日间 08:00-18:00晚间 18:00-22:00夜间 22:00-08:00A0.100.060.02B0.250.150.05C0.530.330.13D0.870.470.17E1.440.800.30注意这个表里三个时段的边界不是随便定的。日间从 08:00 开始到 18:00 结束晚间从 18:00 接着算到 22:00 结束夜间则从 22:00 一直覆盖到第二天早上 08:00。这三个区间正好覆盖满 24 小时不存在“空档”也没有重叠。实际写代码时我会习惯把边界全部换成分钟数来记08:00 48018:00 108022:00 1320。这样后面做跨天计算时会省掉大量判断。1.2 区号前缀决定了你按哪一档收费接下来的问题就是怎么知道一次通话按哪一档来算答案在区号前缀表里。题目一开始会给一串行每行包含一个区号前缀和一个费率档字母。比如1 A 10 B 102 C这意味着拨号前缀是1的号码按 A 档算拨号前缀是10的号码按 B 档算拨号前缀是102的号码按 C 档算。这里有一条非常关键的规则必须匹配最长前缀。也就是说一个电话号码如果以1开头那它确实匹配1但如果它前三位是102必须优先匹配102而不是只匹配到1或者10就停下来。为什么强调这一点因为很多人第一次做这道题时会把区号表放进一个map然后从头到尾找第一个“能匹配开头”的区号。如果表的插入顺序刚好是1、10、102那么号码1023456789就会错误地命中1。这个错误非常隐蔽因为样例数据往往会特意设计成前缀有包含关系你不做最长匹配就直接 WA。2. 输入输出里最容易翻车的三个细节2.1 两段输入都以#结束这道题的输入结构很典型先是一张区号费率映射表然后是一批通话记录。两段输入都以单独一行的#作为结束标记。第一段的每一行格式是[区号前缀] [费率档字母]第二段的每一行格式是[电话号码] [开始时间 HHMM] [通话时长 HHMM]这里有个坏消息如果只用while(cin s)一直读到 EOF你会把#也当成一条数据处理。所以正确姿势是先读一个字符串判断它是不是#再决定继续还是跳出循环。读完后我习惯把第一段存成一个unordered_mapstring, int键是区号前缀字符串值是费率档对应的下标0-4。注意这里的键必须用字符串不能用int原因我下面细说。2.2 开始时间和持续时长都是 HHMM不是普通整数这是非常容易犯错的地方。题目里的时间一律写成四位数字0800表示早上八点零分1730表示下午五点三十分。通话时长也一样0030表示 30 分钟0130表示 1 小时 30 分钟。如果你把0130直接当成普通整数130来用费用就会少算。正确做法是写一个转换函数int toMinute(int hhmm) { return hhmm / 100 * 60 hhmm % 100; }0800经过这个函数变成4800130变成90。所有费用计算都基于分钟不要在后续逻辑里再手动判断“小时”和“分钟”。2.3 输出列宽和补零问题老题的输出通常要求对齐但不同版本要求不太一样。我在下面给的代码里采用一种常见的紧凑表格输出printf(%-10s%-8s%04d%04d%10.2f\n, dialCode.c_str(), localNumber.c_str(), startHHMM, durationHHMM, charge);这里%04d的作用是把开始时间和通话时长补成四位输出。如果输入本身是0800输出也是0800如果你把时间去掉了前导零输出就会少一个零。很多 WA 不是算法错了而是这里补零没到位。3. 前缀匹配与费用计算分钟推演法的完整实现3.1 为什么我推荐一格格推分钟而不是手算分段电话费用最麻烦的地方在于一次通话可能横跨多个费率时段。比如一个电话从17:59开始通话 3 分钟那么第一分钟是日间价第二分钟开始是晚间价。再比如从21:59开始通话 3 分钟最后一分钟已经进入了夜间时段。有些人喜欢先算“整个通话落在哪个时段”再乘时长这是错误思路。正确的思路是把通话的每一分钟拿出来看这一分钟的开始时刻落在哪个区间就按那个区间的费率计费。最朴素也最不容易写错的做法是按分钟循环for (int i 0; i durationMinutes; i) { int cur (startMinutes i) % (24 * 60); if (cur 480 cur 1080) { // 日间 } else if (cur 1080 cur 1320) { // 晚间 } else { // 夜间 } }由于老题里通话时长通常不会超过一天最多就是 1440 个循环完全跑得动。如果你担心性能后面我会给一个更快的按整周期统计的写法但作为入门先把分钟推演法写对再说。3.2 完整 C17 可提交代码下面是一段完整的核心实现。读区号表、读通话记录、最长前缀匹配、跨时段计费都在里面。#include bits/stdc.h using namespace std; const double COST[5][3] { {0.10, 0.06, 0.02}, {0.25, 0.15, 0.05}, {0.53, 0.33, 0.13}, {0.87, 0.47, 0.17}, {1.44, 0.80, 0.30} }; const int DAY_BEGIN 8 * 60; // 480 const int DAY_END 18 * 60; // 1080 const int EVE_END 22 * 60; // 1320 int toMinute(int hhmm) { return hhmm / 100 * 60 hhmm % 100; } double calcCost(int startHHMM, int durationHHMM, int group) { int startMinutes toMinute(startHHMM); // 老题里 duration 通常也是 HHMM例如 0130 表示 90 分钟 int durationMinutes toMinute(durationHHMM); // 如果你拿到的版本把 duration 定义为纯分钟数把上面这一行改成 // int durationMinutes durationHHMM; double ans 0.0; for (int i 0; i durationMinutes; i) { int cur (startMinutes i) % (24 * 60); if (cur DAY_BEGIN cur DAY_END) { ans COST[group][0]; } else if (cur DAY_END cur EVE_END) { ans COST[group][1]; } else { ans COST[group][2]; } } return ans; } int main() { unordered_mapstring, int rateType; string code, category; while (cin code code ! #) { cin category; rateType[code] category[0] - A; } string phone; int startHHMM, durationHHMM; while (cin phone phone ! #) { cin startHHMM durationHHMM; int group -1; string dialCode; // 最长前缀匹配从长到短试命中的第一个就是答案 int maxLen min(5, (int)phone.size()); for (int len maxLen; len 1; --len) { string prefix phone.substr(0, len); auto it rateType.find(prefix); if (it ! rateType.end()) { dialCode prefix; group it-second; break; } } if (group -1) { // 理论上不会走到但出于安全考虑继续处理下一条 continue; } string localNumber phone.substr(dialCode.size()); double charge calcCost(startHHMM, durationHHMM, group); printf(%-10s%-8s%04d%04d%10.2f\n, dialCode.c_str(), localNumber.c_str(), startHHMM, durationHHMM, charge); } return 0; }这段代码没有用到任何高深算法但能稳定跑通核心逻辑。里面有几个点值得再解释一下匹配区号时从min(5, phone.size())开始向前递减天然保证“最长前缀优先”。题目里区号最长 5 位所以这里限制到 5。% (24 * 60)的作用是处理跨天。如果开始时间是23:50通话 20 分钟循环到第 10 分钟时cur会变成0自动进入第二天的日间判断。category[0] - A把A-E映射成下标0-4正好对应COST数组第一维。3.3 关于时间的边界判断我在代码里用的是“左闭右开”区间480 cur 1080 日间 1080 cur 1320 晚间 其余 夜间也就是说08:00这一分钟按日间算18:00这一分钟按晚间算22:00这一分钟按夜间算。如果你写成cur 1080或者cur 1320正好会把边界分钟多算或少算。这类题目不会在样例里把所有边界都测出来但隐藏数据一定会有所以边界必须很敏感。4. 从 WA 到 AC 的查错路径我实际上踩过的坑4.1 把区号当整数读丢了前导零第一次写这题时我觉得区号不就是一个数字吗于是用int读code再用mapint, int存表。结果遇到01这种区号时它变成了1跟另一个区号1冲突后面的匹配全乱套。电话系统里的区号前缀是可以以0开头的甚至可能出现001、0012这种写法。一旦你用整数读前导零就没了。更隐蔽的是电话表中可能同时存在1和01这时两者在整形空间里会变成同一个数字。所以区号前缀、电话号码这两个字段一律按字符串处理。匹配时也用字符串的substr不要手动转成数字。4.2 前缀匹配的顺序不是看表顺序我在最初版本里写过这样的代码for (auto p : rateType) { if (phone.find(p.first) 0) { group p.second; break; } }这在区号互不包含时没问题。可一旦表里有1和102电话号码1024567就会先命中1最后输出结果会差好几倍。后来我改成“按长度从大到小排序再遍历一次”也能解决。但最稳妥的方法还是直接按长度从 5 到 1 枚举前缀。这样做的好处是逻辑直白也不会依赖表的遍历顺序。顺便说一句就算你用map它默认按键的字典序排列而不是按字符串长度排列。所以不要以为放进map就能自动拿到最长匹配。4.3 跨天通话的时段衔接这个坑非常经典。一个通话从21:59:45开始持续 3 分钟真实时间里它跨越了22:00。如果你只用开始时间的小时数去判断整个通话属于夜间还是晚间就会错。正确做法我已经写在代码里了每个分钟都独立判断。为了验证这一点我建议自己手动构造几组极端数据开始 1759时长 3 - 日间 1 分钟 晚间 2 分钟 开始 2159时长 3 - 晚间 1 分钟 夜间 2 分钟 开始 0759时长 3 - 夜间 1 分钟 日间 2 分钟把这三组数据分别手算出期望费用再跑程序对比。一旦能对上跨天逻辑基本就稳了。4.4 浮点数和输出精度费用建议用double累加不要用float。虽然样例看起来差值不大但隐藏数据里可能出现很多分钟的累加float的精度会在四舍五入时出问题。输出时用printf(%.2f, charge)或者fixed setprecision(2)。不要把中间计算结果提前四舍五入否则最后累积误差会被放大。我见过有人每算一分钟就round一次结果最后一位小数经常差 1非常冤。5. 进阶如果通话可以特别长用整周期统计更稳5.1 为什么老题用不上但思路值得掌握老题里通话时长最多也就是一天以内分钟推演法足够。但如果哪一天你遇到“通话时长可能达到 100000 分钟”的变体再逐分钟循环就不太优雅了。好在这类计费模型有一个天然特性每天的收费模式完全一样。一个电话无论从几点开始只要时长超过 1440 分钟就一定会包含若干个完整的 24 小时周期。每个完整周期的费用是固定的日间分钟数 * 日间费率 晚间分钟数 * 晚间费率 夜间分钟数 * 夜间费率其中一天里日间有 10 小时晚间有 4 小时夜间有 10 小时所以一个完整周期费用 600 * dayRate 240 * eveningRate 600 * nightRate于是计算步骤变成把时长拆成fullDays duration / 1440和rem duration % 1440总费用先加上fullDays * 完整周期费用剩下的rem分钟从起始时刻开始逐分钟模拟。这样哪怕通话时长高达几百万分钟也只循环最多 1440 次。5.2 更进一步的做法是纯区间求交如果你连那剩余的 1440 分钟都不想循环也可以把起始时刻对应的三个费率区间画在一条时间轴上然后分别求通话区间与三个费率的交集长度。这个方法对环形时间轴需要小心处理跨天所以我个人觉得“整周期 余数轮询”已经是性价比更高的写法了。无论是用哪种方法核心没有变先把时间转成分钟再对每一分钟单独判断费率。只要这个基本模型不变题目再怎么变都不会跑偏。我自己的习惯是凡是时间模拟题第一步永远把 HHMM 转成分钟凡是编码前缀题永远用字符串。这个习惯就是从这道题开始养成的后来在不少模拟题里都救过我。如果你也正在被这题折磨不妨把上面那段代码跑通然后用我给的三个极端用例自测一下。通了之后你会发现这道老题其实是在教一件事细节比算法更值得敬畏。