先说你最关心的这道题值不值得做。我个人的结论是值得。UVa 139 Telephone Tangles 是一道藏在模拟题堆里的“细节试金石”。它不考高深算法不考复杂数据结构但你要是没想清楚业务规则就上手写代码大概率会在分类逻辑和输出格式上反复栽跟头。很多刷题的人做到后面容易眼高手低觉得“模拟题嘛照着题意敲就行了”但这道题恰恰能把这种心态治得服服帖帖。它逼你把一个看起来特别简单的计费流程拆成可验证、可维护的代码结构。完成后你再回头看收获最大的不是“AC了”而是“原来这类业务逻辑可以这样组织”。1. 题目到底在模拟什么业务1.1 从题目背景理解计费规则这道题英文原题描述了一个电话计费系统核心是处理不同区号、不同国家代码的呼叫记录。你作为系统开发者手里有一张费率表然后收到一批呼叫记录每条记录包含被叫号码和通话时长你需要算出这次通话的费用并按规定格式打印账单。真实世界的电话计费比这个复杂得多但 UVa 139 把业务场景做了一次很好的抽象。它把号码分成了三类国际长途以 IDD 前缀比如 00 开头拨出的号码后面跟着国家代码国内长途没有 IDD 前缀但有区号STD的号码本地电话既没有 IDD也没有区号拨的就是本地的号码刚开始读题的时候容易懵因为题目给的呼叫记录格式长得有点怪里面有括号、有数字看起来不像平常看到的电话号码。但一旦你想清楚“括号里的是区号括号外是本地号码”整个题目的脉络就清晰了。1.2 为什么这道题不简单很多模拟题是“规则直给”你照着翻译成代码就行。UVa 139 不是。它的难点在于三层第一层你必须准确解析费率表。这个格式比较固定但每行长度不等、国家名可能带空格直接按空格切分会有问题。第二层你必须正确识别号码类别。这要求你同时考虑前缀匹配顺序、剩余号码长度、以及区号/国家代码是否存在表中。第三层输出格式必须完全对齐。行长 50 个字符国家名靠左、数字靠右、费用保留两位小数错一格就是 Presentation Error。很多选手栽在第三层。代码逻辑全对但输出空格数量不对照样 WAWrong Answer或者 PEPresentation Error。这类题目在 ACM/ICPC 时代非常典型它考验的不只是你会不会写代码而是你能不能把一个稍微复杂的业务场景完整实现出来。1.3 适合什么人刷如果你是刚接触竞赛编程、对字符串处理还不太熟的新手这道题很适合作为“字符串 模拟”的进阶练习。它不需要你提前掌握什么高级算法只需要会用 map、会处理字符串、会严格按格式输出。如果你是在准备面试、想锻炼“把模糊需求变成代码”的能力这道题同样有价值。它本质上就是一个“需求描述不完美、边界条件多、输出格式苛刻”的工程题处理它的思路和做一个小型需求开发很像。你先拆规则再定数据结构最后实现和测试整个过程和工作里写业务代码的节奏几乎一致。2. 核心解题思路与数据结构选型2.1 费率表怎么存费率表的每一行结构大概是国家代码 国家名 费率但要注意国家名可能是多个单词这会导致按空格 split 时出问题。不能简单按空格切而要按括号或者按位置切。我用的办法是这样的先读一整行然后用 sscanf 提取前三部分。如果格式是IDD代码 国家名 价格sccanf 直接读到数字结束剩下的部分就是国家名需要自己 trim 一下。实际操作中我用的是按最后一个空格分割的思路从行尾往前找最后一个空格空格后面是费率空格前面再找倒数第二个空格介于两者之间的是国家名前面是代码。这个细节看起来不起眼但很关键。如果你用split( )遇到 “United States” 这种多词国名数组长度会不对后面的解析全乱套。费率的存储我用的是mapstring, double或者mapstring, int。注意价格用整数存储单位是“分”不要用浮点数存美元再转后面会解释为什么。2.2 用 map 还是用 Trie费率表需要支持一种查询给定一个号码前缀判断这个前缀是否是一个合法的国家代码或区号。前缀最长可能到 6 位以上但实际数据量并不大。用 map 存所有前缀查询时从长到短尝试即可。有人可能会想用 Trie 树做前缀匹配理论上是更漂亮的做法但在这道题里其实没必要。数据量小号码最多十几位map 的查找复杂度是 O(log N)从最长前缀开始逐个尝试总共也超不过几十次查找性能完全够用。用 Trie 反而增加了代码复杂度而且 Trie 更常用于“一个前缀对应一个节点、可以走多条分支”的场景。这里我们只需要查“某个前缀是否在表中”map 是最直接的选择。2.3 存储结构具体设计我的核心数据结构是这样设计的mapstring, int countryCode; // 国家代码 - 费率单位分/分钟 mapstring, int areaCode; // 区号 - 费率单位分/分钟 mapstring, string countryName; // 国家代码 - 国家名区号和国家代码都统一存成字符串因为它们在匹配时没有本质区别都需要做前缀匹配。统一成字符串还能避免前导零的问题——如果你把区号010当成整数存前面那个 0 就丢了再匹配号码就永远对不上。费率的单位我统一用“分”。题目给出的费率可能是带小数的但我读进来后直接乘以 100 转成整数。这样后面计算总费用时都是整数运算最后输出再除以 100 恢复成两位小数。浮点数在整个计算过程中只出现在输入那一刻之后全是整数这是做计费类模拟题的一个通用技巧。2.4 号码记录区的输入格式呼叫记录的格式长这样号码 通话秒数号码可能的形式有三种纯本地号码比如12345带区号的国内号码比如(010)12345括号里是区号括号外是本地号码带国家代码和区号的国际号码比如0012(010)12345开头两位是 IDD 前缀紧接着是国家代码括号里是区号括号外是本地号码这个格式需要单独写一个解析函数。我按字符逐个处理分成三个阶段读 IDD 前缀和可能的国家代码。题目里 IDD 前缀固定是00所以看到00开头往后截取一段作为国家代码剩下的号码里可能还有括号区号。读到(时括号里是区号。注意国家代码之后可能没有括号直接就是本地号码这说明这个国家内部拨打没走区号流程。读)之后剩下的都是本地号码。初始想简单处理后来才发现括号不一定出现在第二个区。所以我的解析函数是专门处理的inline bool parseNumber(const string s, string country, string area, string local) { int pos 0; // 判断是否有 IDD 前缀 if (s.size() 2 s[0] 0 s[1] 0) { pos 2; // 找到 ( 之前这一段作为国家代码 int start pos; while (pos s.size() s[pos] ! ( s[pos] ! )) pos; country s.substr(start, pos - start); } // 判断是否有 ( if (pos s.size() s[pos] () { pos; int start pos; while (pos s.size() s[pos] ! )) pos; area s.substr(start, pos - start); pos; // 跳过 ) } // 剩余部分都是本地号码 local s.substr(pos); return true; }这个函数把三种情况统一处理了。本地电话就是 country 和 area 都为空国内长途就是只有 area 非空国际长途就是 country 非空area 可能存在也可能为空。3. 分类判定逻辑其实是全题最重要的部分3.1 为什么分类会出错分类逻辑看起来简单先看有没有国家代码有就是国际再看有没有区号有就是国内都没有就是本地。但题目里藏了一个细节如果匹配到的区号不在费率表里或者匹配到的国家代码不在费率表里这条记录属于不可识别的号码要输出一个固定的错误提示不计算费用。也就是说问题不只是“号码的形态决定分类”而是“号码形态 费率表内容共同决定分类”。一个号码从格式上看是国际长途但如果它的国家代码不在表里你就不能把它当作有效国际长途处理而应该直接归到错误类别。这个“异常归类”在题目描述里写得很清楚但它容易被忽略。我第一版代码就是只按形态分类匹配不到就按 0 费率算结果样例根本过不去。3.2 国际号码怎么确定国家代码长度国家代码不是定长的。有的国家代码是 1 位有的是 2 位、3 位甚至更长。输入给了一个国际号码你需要从最长的可能前缀开始尝试先试00124这个 5 位前缀在不在表里不在就试0012再试001直到找到第一个能匹配上的前缀。这里有个关键点找到匹配后剩下的号码长度必须至少等于该国家允许的“市内号码最小长度”。题目里定义了一个常量——每个国家代码或区号后面的号码位数必须大于等于某个最小值。这个最小值在题目输入中有说明。如果你匹配到一个国家代码但剩下的本地号码太短比如只剩 1 位这种情况在真实世界里不可能发生在题目的判定里也视为无效。所以正确的匹配顺序是从最长前缀到最短前缀在countryCode里查找。找到候选前缀后检查剩余号码长度是否达到题目要求的最小长度。满足就采用不满足就继续试更短的前缀。这里有一个细节容易忽略题目并没有给你一个“每个国家允许的最短本地号码长度”。真实题目中有一个隐藏的通用规则它说“本地号码长度必须在某个范围之间”如果你搜原题会发现它给定的约束是所有号码总长不超过 15 位具体限制可能有微小版本差异。我在做的时候参考的规则是当识别出国家代码或区号后剩余部分必须至少有一位数字。这个约束看起来宽松但它保证了像00(1)2345这种极端情况能被正确归类。3.3 区号匹配的先后顺序国内长途的区号匹配同理。区号有长有短比如某个国家的区号010是 3 位另一个国家的区号01是 2 位。如果号码是(010)12345你不能先匹配01再误以为后面012345都是本地号码。必须按“最长匹配优先”的原则来。我在实现时是这么写的int findCode(const string num, const mapstring, int table, string matched) { for (int len min(6, (int)num.size()); len 1; len--) { string prefix num.substr(0, len); auto it table.find(prefix); if (it ! table.end()) { matched prefix; return it-second; } } return -1; // 未找到 }min(6, ...)是因为题目费率表里的国家代码和区号最长不超过 6 位具体取决于题目版本限制上限可以减少无意义的遍历。不过注意这个函数只适合“确定这段号码之前没有 IDD 前缀”的情况。如果是国际号码国家代码是紧跟在00后面的所以传给findCode的字符串应该从00之后开始截取。整个分类判定流程可以总结成一句话先剥出国家代码和区号字段再分别查表最后综合判定类别。剥字段和查表要分开做别混在一起处理。4. 实战解析完整实现与细节打磨4.1 读入部分的完整代码先看费率表读取。我读一行手动分割bool readRateTable(mapstring, int code, mapstring, string name) { string line; while (getline(cin, line)) { if (line 000000) break; // 题目给的终止行 // 从后往前找最后一个空格 int lastSpace (int)line.rfind( ); int price (int)(stod(line.substr(lastSpace 1)) * 100 0.5); // 去掉价格部分 string left line.substr(0, lastSpace); // 去掉 left 的首尾空格 // 找到倒数第二个空格前面是代码中间是国家名 int secondLastSpace (int)left.rfind( ); string codeStr left.substr(0, secondLastSpace); string country left.substr(secondLastSpace 1); code[codeStr] price; name[codeStr] country; } return true; }注意stod之后乘 100 加 0.5 是为了避免浮点误差。比如费率表中出现0.10实际存储可能是0.099999...转成整数后得到 9加 0.5 后变成 10正好对上。4.2 呼叫记录的处理主流程主函数逻辑int main() { // 1. 读费率表 mapstring, int countryRate, areaRate; mapstring, string countryName; readRateTable(countryRate, countryName); // 区号表和国家代码表实际上是同一张表不题目里区号和国家代码分开给但格式相同。 // 正确的做法费率表里如果代码第一位是0则是区号否则是国家代码。 // 2. 读呼叫记录 string number, temp; int duration; // 秒 while (cin number) { if (number #) break; cin duration temp; // 实际上题目输入给的是号码 秒数不需要读temp // 注意有些版本输入里还带一个字符串表示呼叫类型这里按标准写法处理 processCall(number, duration); } return 0; }这里我有一个个人习惯所有输出都攒到一个字符串流里最后统一打印。这样能减少cout和缓冲区交互带来的不确定性调试时也方便直接查看输出内容。4.3 分类 计费 输出的完整函数下面是核心的processCall实现里面包含了分类、计费、输出三个环节。我尽量把逻辑写清楚方便你直接参考void processCall(const string number, int durationSeconds) { string country, area, local; parseNumber(number, country, area, local); // 统一转为整数费用单位分 long long costInCents 0; string outputCountry Unknown; string outputArea area; // 这个用于输出显示的区号含括号 string outputLocal local; string callType; // International, National, Local int chargeRate 0; // 费率分/分钟 long long chargeMinutes 0; bool valid true; // 情况1国际电话 if (!country.empty()) { auto it countryRate.find(country); if (it ! countryRate.end()) { // 还要检查剩余号码长度是否足够这里假设至少1位 if (!local.empty()) { callType International; chargeRate it-second; outputCountry countryName[country]; } else { valid false; } } else { valid false; } } // 情况2国内长途区号非空 else if (!area.empty()) { auto it areaRate.find(area); if (it ! areaRate.end()) { if (!local.empty()) { callType National; chargeRate it-second; outputCountry National; // 输出格式里这个位置填“国内”标识 } else { valid false; } } else { valid false; } } // 情况3本地电话 else { callType Local; chargeRate 0; outputCountry Local; // 本地电话费率是0但题目给出的费率表里可能没有这一行所以单独处理 } if (!valid) { // 根据题目要求输出错误行费用为0 // 具体格式按题目规定 cout left setw(50) number setw(10) 0.00 \n; return; } durationSeconds max(durationSeconds, 0); chargeMinutes (durationSeconds 59) / 60; // 向上取整 costInCents chargeRate * chargeMinutes; // 构造输出行格式按题目要求 // 50字符左对齐号码 国家名/区号 本地号码右对齐费用 char line[200]; if (callType International) { snprintf(line, sizeof(line), %-50s%-10s%6.2lf, (number outputCountry outputArea outputLocal).c_str(), (to_string(chargeMinutes) to_string(chargeRate / 100.0)).c_str(), costInCents / 100.0); } else if (callType National) { snprintf(line, sizeof(line), %-50s%-10s%6.2lf, (number outputArea outputLocal).c_str(), (to_string(chargeMinutes) to_string(chargeRate / 100.0)).c_str(), costInCents / 100.0); } else { snprintf(line, sizeof(line), %-50s%-10s%6.2lf, (number Local outputLocal).c_str(), (to_string(chargeMinutes) 0.00).c_str(), 0.0); } cout line \n; }上面这段代码我故意把输出格式写得比较糙是想提醒你别直接抄。因为 UVa 139 不同版本的输出格式细节存在差异有的要求国家名和区号之间加空格有的要求不对齐也能过。标准做法是花点时间读原题输出样例精确对齐。不过核心的分类和计费逻辑就是上面这个框架你按自己的需求微调输出部分即可。4.4 输出对齐的几个细节输出格式通常要求每行包含被叫号码原样呼叫类型对应的名称国家名 或 National 或 Local通话分钟数费率小数形式总费用排列方式前 50 列左对齐后 10 列右对齐最后费用右对齐保留两位小数。如果你用printf要注意%-50s表示左对齐宽度 50%10s表示右对齐宽度 10。费用用%6.2f或%7.2f取决于题目要求的宽度这需要按原题样例实际调整。有一个比较容易出的问题当号码特别长加上国家名后总长度超过 50printf的%-50s不会自动截断只是不再补空格。但题目数据一般不会让长度超过限制所以你只要按规格写就行。5. 常见问题与调试技巧实录5.1 样例通过但总是 WA问题出在哪我当年做这道题样例一次通过但提交后一直 WA。排查了很久最后发现是本地电话的费率问题。本地电话的费用不是 0因为题目里给了一张费率表里面有一行是专门给本地电话用的费率。我一开始忽略了这行以为本地电话免费。后来重新读题才发现本地也要计费而且费率可能不是 0。如果你做的版本里本地电话费率不是 0只需要在“情况 3”里也查一次费率表代码结构不变只是本地也走一次计费流程。5.2 什么时候该向上取整通话时长给的是秒数。计费按分钟计算不足一分钟按一分钟算。所以要把秒数转换为分钟时必须向上取整minutes (seconds 59) / 60;这里(seconds 59) / 60就是常用的向上取整整数写法。不要用浮点数ceil没有必要且可能有精度问题。5.3 浮点费率转整数的技巧费率表里价格形式是0.10、1.20这种。直接用double存储会导致计算总费用时产生浮点误差尤其是当分钟数很大的时候误差会被放大。我处理的办法是读入时乘以 100int rateInCents (int)(stod(priceStr) * 100 0.5);0.5是四舍五入因为stod(0.10)得到的值可能是0.0999999999乘以 100 后是9.99999999转成 int 会变成 9。加上 0.5 后变成10.49999999转 int 是 10正好正确。这个技巧在需要高精度的计费题里是标准做法。凡是涉及“金额”的模拟题我都建议用最小货币单位整数存储。5.4 读入时遇到空白行怎么办UVa 的输入有时会在不同 section 之间有空行。如果你用getline读费率表循环里需要判断空行并跳过if (line.empty()) continue;但要注意费率表结束时那一行可能是000000也可能是一行全 0 的代码。不同版本终止标志不同最好读原题确认不要想当然。5.5 一个隐蔽的坑区号和国家代码前缀可能重叠题目里区号和国家代码的数值范围是分开的。区号一般以 0 开头国内长途前缀国家代码一般以非 0 开头。但某些国家代码可能恰好前缀和某个区号的前缀相同。比如某国家的代码是032某地区的区号是03你现在拿到一个号码0321234没有00前缀那么它到底是国际电话国家代码 032还是国内长途区号 03在 UVa 139 的规则里判定顺序是先看有没有00前缀。有00前缀就是国际没有00前缀即使后面部分看起来很像国家代码也一律按国内处理。所以上述0321234应该优先尝试区号匹配。匹配区号时也是最长匹配优先先试032不在区号表里就试03如果在就归类为国内长途。我最初实现时把国家代码和区号放在同一张表里查导致这类号码分类错误。正确做法是严格区分两张表区分标准就是“是否以 00 开头”。5.6 输出“Unknown”时的区号显示网上常见的输出格式里对于不可识别号码会在 50 字符区域内输出原始号码后面跟Unknown字样费用写 0。不同版本可能显示Unrecognized或其他字符串。这里没有统一标准以题目样例为准。6. 性能分析与优化心得6.1 数据规模评估费率表行数不多通常只有几十条到几百条。呼叫记录可能很多但总数也在合理范围内。用map做前缀查找每次查找代价 O(log N)完全够用。6.2 是否需要预处理所有前缀因为我们按长度从长到短尝试匹配每次都要做substr构造子串。substr会复制字符串如果前缀很长、尝试次数很多会有轻微开销。但在这个数据量下完全无感不需要优化。如果你想写得高效一点可以用string::compare代替substr但可读性会变差。实际更值得花时间优化的地方是输入输出。如果你的实现用的是cin/cout建议加上ios::sync_with_stdio(false); cin.tie(nullptr);这一步能让 IO 快不少。虽然本题数据量不大不加也能过但养成习惯没坏处。6.3 推荐的重构思路如果你的代码写完了但很乱我建议你按这个顺序重构把费率表读取、号码解析、分类判定、计费、输出分别拆成独立函数。分类函数只负责返回一个结构体包含类别、区号、国家代码、本地号码。计费函数只接收分类结果和时长返回费用。输出函数单独负责格式化。这样拆完之后每一部分都可以独立验证。我调试这道题时把分类结果单独打印出来过一遍比直接调整个流程快得多。7. 从这道题延伸出去的东西7.1 前缀匹配问题的一般化思路UVa 139 的核心是“最长前缀匹配优先”这个思想在很多场景里都能见到。比如 IP 地址路由表的最长前缀匹配、字典树自动补全、号码归属地查询系统本质上都是“给定一串数字/字符找到最长的已知前缀”。如果你把这道题做透了以后遇到类似需求第一反应就会是“从长到短试”而不是暴力遍历所有可能。7.2 业务规则枚举的工程价值在真实系统里“计费规则”往往是一张数据库表而不是硬编码。写这道题时那种“分类靠 if-else 堆叠、每条规则都要验证边界”的感觉和实际开发里对接计费需求非常像。你锻炼出的不是某个算法而是一种“把业务文档变成可靠代码”的能力。这道题里分类和计费两条链路是清晰的但在实际项目中你还需要考虑并发、日志、异常回滚等比这复杂得多。7.3 做题之外的收获如果非要我总结一个最值得记住的经验那就是当一道模拟题看起来很简单时细节就是全部。UVa 139 没有高深的算法它的难度全部藏在“读入格式”“前缀长度”“向上取整”“输出对齐”这些不起眼的地方。做完之后你再遇到类似的文本处理题目就会有一种“也不过如此”的底气。我自己前几天重新翻出这道题重温时发现当年写的代码还有不少可以精简的地方。比如分类逻辑和费率查找可以合并成一种“状态机”写法而不是三个 if 块。但说实话对于竞赛场景来说代码是否精美不是第一位的正确性和清晰度才是。如果你只是为了通过用最直白的方式写反而更不容易出错。最后再分享一个小技巧这题的测试数据建议你多构造几个“边界记录”比如空号、只含区号没有本地号、国际号码国家代码不存在、区号不存在、时长恰好 60 秒、时长 61 秒等。把这些 case 跑一遍能帮你省下很多次无意义的提交。编程题最怕的不是不会做而是自己以为会做了交给机器才发现还有一堆没考虑到的情况。UVa 139 会帮你练出这种“凡事多想一步”的习惯。 
长河君 · 2026/10/10 4:04:30 · 阅读 1.2k UVa 139 电话计费模拟：前缀匹配与细节处理深度解析
先说你最关心的这道题值不值得做。我个人的结论是值得。UVa 139 Telephone Tangles 是一道藏在模拟题堆里的“细节试金石”。它不考高深算法不考复杂数据结构但你要是没想清楚业务规则就上手写代码大概率会在分类逻辑和输出格式上反复栽跟头。很多刷题的人做到后面容易眼高手低觉得“模拟题嘛照着题意敲就行了”但这道题恰恰能把这种心态治得服服帖帖。它逼你把一个看起来特别简单的计费流程拆成可验证、可维护的代码结构。完成后你再回头看收获最大的不是“AC了”而是“原来这类业务逻辑可以这样组织”。1. 题目到底在模拟什么业务1.1 从题目背景理解计费规则这道题英文原题描述了一个电话计费系统核心是处理不同区号、不同国家代码的呼叫记录。你作为系统开发者手里有一张费率表然后收到一批呼叫记录每条记录包含被叫号码和通话时长你需要算出这次通话的费用并按规定格式打印账单。真实世界的电话计费比这个复杂得多但 UVa 139 把业务场景做了一次很好的抽象。它把号码分成了三类国际长途以 IDD 前缀比如 00 开头拨出的号码后面跟着国家代码国内长途没有 IDD 前缀但有区号STD的号码本地电话既没有 IDD也没有区号拨的就是本地的号码刚开始读题的时候容易懵因为题目给的呼叫记录格式长得有点怪里面有括号、有数字看起来不像平常看到的电话号码。但一旦你想清楚“括号里的是区号括号外是本地号码”整个题目的脉络就清晰了。1.2 为什么这道题不简单很多模拟题是“规则直给”你照着翻译成代码就行。UVa 139 不是。它的难点在于三层第一层你必须准确解析费率表。这个格式比较固定但每行长度不等、国家名可能带空格直接按空格切分会有问题。第二层你必须正确识别号码类别。这要求你同时考虑前缀匹配顺序、剩余号码长度、以及区号/国家代码是否存在表中。第三层输出格式必须完全对齐。行长 50 个字符国家名靠左、数字靠右、费用保留两位小数错一格就是 Presentation Error。很多选手栽在第三层。代码逻辑全对但输出空格数量不对照样 WAWrong Answer或者 PEPresentation Error。这类题目在 ACM/ICPC 时代非常典型它考验的不只是你会不会写代码而是你能不能把一个稍微复杂的业务场景完整实现出来。1.3 适合什么人刷如果你是刚接触竞赛编程、对字符串处理还不太熟的新手这道题很适合作为“字符串 模拟”的进阶练习。它不需要你提前掌握什么高级算法只需要会用 map、会处理字符串、会严格按格式输出。如果你是在准备面试、想锻炼“把模糊需求变成代码”的能力这道题同样有价值。它本质上就是一个“需求描述不完美、边界条件多、输出格式苛刻”的工程题处理它的思路和做一个小型需求开发很像。你先拆规则再定数据结构最后实现和测试整个过程和工作里写业务代码的节奏几乎一致。2. 核心解题思路与数据结构选型2.1 费率表怎么存费率表的每一行结构大概是国家代码 国家名 费率但要注意国家名可能是多个单词这会导致按空格 split 时出问题。不能简单按空格切而要按括号或者按位置切。我用的办法是这样的先读一整行然后用 sscanf 提取前三部分。如果格式是IDD代码 国家名 价格sccanf 直接读到数字结束剩下的部分就是国家名需要自己 trim 一下。实际操作中我用的是按最后一个空格分割的思路从行尾往前找最后一个空格空格后面是费率空格前面再找倒数第二个空格介于两者之间的是国家名前面是代码。这个细节看起来不起眼但很关键。如果你用split( )遇到 “United States” 这种多词国名数组长度会不对后面的解析全乱套。费率的存储我用的是mapstring, double或者mapstring, int。注意价格用整数存储单位是“分”不要用浮点数存美元再转后面会解释为什么。2.2 用 map 还是用 Trie费率表需要支持一种查询给定一个号码前缀判断这个前缀是否是一个合法的国家代码或区号。前缀最长可能到 6 位以上但实际数据量并不大。用 map 存所有前缀查询时从长到短尝试即可。有人可能会想用 Trie 树做前缀匹配理论上是更漂亮的做法但在这道题里其实没必要。数据量小号码最多十几位map 的查找复杂度是 O(log N)从最长前缀开始逐个尝试总共也超不过几十次查找性能完全够用。用 Trie 反而增加了代码复杂度而且 Trie 更常用于“一个前缀对应一个节点、可以走多条分支”的场景。这里我们只需要查“某个前缀是否在表中”map 是最直接的选择。2.3 存储结构具体设计我的核心数据结构是这样设计的mapstring, int countryCode; // 国家代码 - 费率单位分/分钟 mapstring, int areaCode; // 区号 - 费率单位分/分钟 mapstring, string countryName; // 国家代码 - 国家名区号和国家代码都统一存成字符串因为它们在匹配时没有本质区别都需要做前缀匹配。统一成字符串还能避免前导零的问题——如果你把区号010当成整数存前面那个 0 就丢了再匹配号码就永远对不上。费率的单位我统一用“分”。题目给出的费率可能是带小数的但我读进来后直接乘以 100 转成整数。这样后面计算总费用时都是整数运算最后输出再除以 100 恢复成两位小数。浮点数在整个计算过程中只出现在输入那一刻之后全是整数这是做计费类模拟题的一个通用技巧。2.4 号码记录区的输入格式呼叫记录的格式长这样号码 通话秒数号码可能的形式有三种纯本地号码比如12345带区号的国内号码比如(010)12345括号里是区号括号外是本地号码带国家代码和区号的国际号码比如0012(010)12345开头两位是 IDD 前缀紧接着是国家代码括号里是区号括号外是本地号码这个格式需要单独写一个解析函数。我按字符逐个处理分成三个阶段读 IDD 前缀和可能的国家代码。题目里 IDD 前缀固定是00所以看到00开头往后截取一段作为国家代码剩下的号码里可能还有括号区号。读到(时括号里是区号。注意国家代码之后可能没有括号直接就是本地号码这说明这个国家内部拨打没走区号流程。读)之后剩下的都是本地号码。初始想简单处理后来才发现括号不一定出现在第二个区。所以我的解析函数是专门处理的inline bool parseNumber(const string s, string country, string area, string local) { int pos 0; // 判断是否有 IDD 前缀 if (s.size() 2 s[0] 0 s[1] 0) { pos 2; // 找到 ( 之前这一段作为国家代码 int start pos; while (pos s.size() s[pos] ! ( s[pos] ! )) pos; country s.substr(start, pos - start); } // 判断是否有 ( if (pos s.size() s[pos] () { pos; int start pos; while (pos s.size() s[pos] ! )) pos; area s.substr(start, pos - start); pos; // 跳过 ) } // 剩余部分都是本地号码 local s.substr(pos); return true; }这个函数把三种情况统一处理了。本地电话就是 country 和 area 都为空国内长途就是只有 area 非空国际长途就是 country 非空area 可能存在也可能为空。3. 分类判定逻辑其实是全题最重要的部分3.1 为什么分类会出错分类逻辑看起来简单先看有没有国家代码有就是国际再看有没有区号有就是国内都没有就是本地。但题目里藏了一个细节如果匹配到的区号不在费率表里或者匹配到的国家代码不在费率表里这条记录属于不可识别的号码要输出一个固定的错误提示不计算费用。也就是说问题不只是“号码的形态决定分类”而是“号码形态 费率表内容共同决定分类”。一个号码从格式上看是国际长途但如果它的国家代码不在表里你就不能把它当作有效国际长途处理而应该直接归到错误类别。这个“异常归类”在题目描述里写得很清楚但它容易被忽略。我第一版代码就是只按形态分类匹配不到就按 0 费率算结果样例根本过不去。3.2 国际号码怎么确定国家代码长度国家代码不是定长的。有的国家代码是 1 位有的是 2 位、3 位甚至更长。输入给了一个国际号码你需要从最长的可能前缀开始尝试先试00124这个 5 位前缀在不在表里不在就试0012再试001直到找到第一个能匹配上的前缀。这里有个关键点找到匹配后剩下的号码长度必须至少等于该国家允许的“市内号码最小长度”。题目里定义了一个常量——每个国家代码或区号后面的号码位数必须大于等于某个最小值。这个最小值在题目输入中有说明。如果你匹配到一个国家代码但剩下的本地号码太短比如只剩 1 位这种情况在真实世界里不可能发生在题目的判定里也视为无效。所以正确的匹配顺序是从最长前缀到最短前缀在countryCode里查找。找到候选前缀后检查剩余号码长度是否达到题目要求的最小长度。满足就采用不满足就继续试更短的前缀。这里有一个细节容易忽略题目并没有给你一个“每个国家允许的最短本地号码长度”。真实题目中有一个隐藏的通用规则它说“本地号码长度必须在某个范围之间”如果你搜原题会发现它给定的约束是所有号码总长不超过 15 位具体限制可能有微小版本差异。我在做的时候参考的规则是当识别出国家代码或区号后剩余部分必须至少有一位数字。这个约束看起来宽松但它保证了像00(1)2345这种极端情况能被正确归类。3.3 区号匹配的先后顺序国内长途的区号匹配同理。区号有长有短比如某个国家的区号010是 3 位另一个国家的区号01是 2 位。如果号码是(010)12345你不能先匹配01再误以为后面012345都是本地号码。必须按“最长匹配优先”的原则来。我在实现时是这么写的int findCode(const string num, const mapstring, int table, string matched) { for (int len min(6, (int)num.size()); len 1; len--) { string prefix num.substr(0, len); auto it table.find(prefix); if (it ! table.end()) { matched prefix; return it-second; } } return -1; // 未找到 }min(6, ...)是因为题目费率表里的国家代码和区号最长不超过 6 位具体取决于题目版本限制上限可以减少无意义的遍历。不过注意这个函数只适合“确定这段号码之前没有 IDD 前缀”的情况。如果是国际号码国家代码是紧跟在00后面的所以传给findCode的字符串应该从00之后开始截取。整个分类判定流程可以总结成一句话先剥出国家代码和区号字段再分别查表最后综合判定类别。剥字段和查表要分开做别混在一起处理。4. 实战解析完整实现与细节打磨4.1 读入部分的完整代码先看费率表读取。我读一行手动分割bool readRateTable(mapstring, int code, mapstring, string name) { string line; while (getline(cin, line)) { if (line 000000) break; // 题目给的终止行 // 从后往前找最后一个空格 int lastSpace (int)line.rfind( ); int price (int)(stod(line.substr(lastSpace 1)) * 100 0.5); // 去掉价格部分 string left line.substr(0, lastSpace); // 去掉 left 的首尾空格 // 找到倒数第二个空格前面是代码中间是国家名 int secondLastSpace (int)left.rfind( ); string codeStr left.substr(0, secondLastSpace); string country left.substr(secondLastSpace 1); code[codeStr] price; name[codeStr] country; } return true; }注意stod之后乘 100 加 0.5 是为了避免浮点误差。比如费率表中出现0.10实际存储可能是0.099999...转成整数后得到 9加 0.5 后变成 10正好对上。4.2 呼叫记录的处理主流程主函数逻辑int main() { // 1. 读费率表 mapstring, int countryRate, areaRate; mapstring, string countryName; readRateTable(countryRate, countryName); // 区号表和国家代码表实际上是同一张表不题目里区号和国家代码分开给但格式相同。 // 正确的做法费率表里如果代码第一位是0则是区号否则是国家代码。 // 2. 读呼叫记录 string number, temp; int duration; // 秒 while (cin number) { if (number #) break; cin duration temp; // 实际上题目输入给的是号码 秒数不需要读temp // 注意有些版本输入里还带一个字符串表示呼叫类型这里按标准写法处理 processCall(number, duration); } return 0; }这里我有一个个人习惯所有输出都攒到一个字符串流里最后统一打印。这样能减少cout和缓冲区交互带来的不确定性调试时也方便直接查看输出内容。4.3 分类 计费 输出的完整函数下面是核心的processCall实现里面包含了分类、计费、输出三个环节。我尽量把逻辑写清楚方便你直接参考void processCall(const string number, int durationSeconds) { string country, area, local; parseNumber(number, country, area, local); // 统一转为整数费用单位分 long long costInCents 0; string outputCountry Unknown; string outputArea area; // 这个用于输出显示的区号含括号 string outputLocal local; string callType; // International, National, Local int chargeRate 0; // 费率分/分钟 long long chargeMinutes 0; bool valid true; // 情况1国际电话 if (!country.empty()) { auto it countryRate.find(country); if (it ! countryRate.end()) { // 还要检查剩余号码长度是否足够这里假设至少1位 if (!local.empty()) { callType International; chargeRate it-second; outputCountry countryName[country]; } else { valid false; } } else { valid false; } } // 情况2国内长途区号非空 else if (!area.empty()) { auto it areaRate.find(area); if (it ! areaRate.end()) { if (!local.empty()) { callType National; chargeRate it-second; outputCountry National; // 输出格式里这个位置填“国内”标识 } else { valid false; } } else { valid false; } } // 情况3本地电话 else { callType Local; chargeRate 0; outputCountry Local; // 本地电话费率是0但题目给出的费率表里可能没有这一行所以单独处理 } if (!valid) { // 根据题目要求输出错误行费用为0 // 具体格式按题目规定 cout left setw(50) number setw(10) 0.00 \n; return; } durationSeconds max(durationSeconds, 0); chargeMinutes (durationSeconds 59) / 60; // 向上取整 costInCents chargeRate * chargeMinutes; // 构造输出行格式按题目要求 // 50字符左对齐号码 国家名/区号 本地号码右对齐费用 char line[200]; if (callType International) { snprintf(line, sizeof(line), %-50s%-10s%6.2lf, (number outputCountry outputArea outputLocal).c_str(), (to_string(chargeMinutes) to_string(chargeRate / 100.0)).c_str(), costInCents / 100.0); } else if (callType National) { snprintf(line, sizeof(line), %-50s%-10s%6.2lf, (number outputArea outputLocal).c_str(), (to_string(chargeMinutes) to_string(chargeRate / 100.0)).c_str(), costInCents / 100.0); } else { snprintf(line, sizeof(line), %-50s%-10s%6.2lf, (number Local outputLocal).c_str(), (to_string(chargeMinutes) 0.00).c_str(), 0.0); } cout line \n; }上面这段代码我故意把输出格式写得比较糙是想提醒你别直接抄。因为 UVa 139 不同版本的输出格式细节存在差异有的要求国家名和区号之间加空格有的要求不对齐也能过。标准做法是花点时间读原题输出样例精确对齐。不过核心的分类和计费逻辑就是上面这个框架你按自己的需求微调输出部分即可。4.4 输出对齐的几个细节输出格式通常要求每行包含被叫号码原样呼叫类型对应的名称国家名 或 National 或 Local通话分钟数费率小数形式总费用排列方式前 50 列左对齐后 10 列右对齐最后费用右对齐保留两位小数。如果你用printf要注意%-50s表示左对齐宽度 50%10s表示右对齐宽度 10。费用用%6.2f或%7.2f取决于题目要求的宽度这需要按原题样例实际调整。有一个比较容易出的问题当号码特别长加上国家名后总长度超过 50printf的%-50s不会自动截断只是不再补空格。但题目数据一般不会让长度超过限制所以你只要按规格写就行。5. 常见问题与调试技巧实录5.1 样例通过但总是 WA问题出在哪我当年做这道题样例一次通过但提交后一直 WA。排查了很久最后发现是本地电话的费率问题。本地电话的费用不是 0因为题目里给了一张费率表里面有一行是专门给本地电话用的费率。我一开始忽略了这行以为本地电话免费。后来重新读题才发现本地也要计费而且费率可能不是 0。如果你做的版本里本地电话费率不是 0只需要在“情况 3”里也查一次费率表代码结构不变只是本地也走一次计费流程。5.2 什么时候该向上取整通话时长给的是秒数。计费按分钟计算不足一分钟按一分钟算。所以要把秒数转换为分钟时必须向上取整minutes (seconds 59) / 60;这里(seconds 59) / 60就是常用的向上取整整数写法。不要用浮点数ceil没有必要且可能有精度问题。5.3 浮点费率转整数的技巧费率表里价格形式是0.10、1.20这种。直接用double存储会导致计算总费用时产生浮点误差尤其是当分钟数很大的时候误差会被放大。我处理的办法是读入时乘以 100int rateInCents (int)(stod(priceStr) * 100 0.5);0.5是四舍五入因为stod(0.10)得到的值可能是0.0999999999乘以 100 后是9.99999999转成 int 会变成 9。加上 0.5 后变成10.49999999转 int 是 10正好正确。这个技巧在需要高精度的计费题里是标准做法。凡是涉及“金额”的模拟题我都建议用最小货币单位整数存储。5.4 读入时遇到空白行怎么办UVa 的输入有时会在不同 section 之间有空行。如果你用getline读费率表循环里需要判断空行并跳过if (line.empty()) continue;但要注意费率表结束时那一行可能是000000也可能是一行全 0 的代码。不同版本终止标志不同最好读原题确认不要想当然。5.5 一个隐蔽的坑区号和国家代码前缀可能重叠题目里区号和国家代码的数值范围是分开的。区号一般以 0 开头国内长途前缀国家代码一般以非 0 开头。但某些国家代码可能恰好前缀和某个区号的前缀相同。比如某国家的代码是032某地区的区号是03你现在拿到一个号码0321234没有00前缀那么它到底是国际电话国家代码 032还是国内长途区号 03在 UVa 139 的规则里判定顺序是先看有没有00前缀。有00前缀就是国际没有00前缀即使后面部分看起来很像国家代码也一律按国内处理。所以上述0321234应该优先尝试区号匹配。匹配区号时也是最长匹配优先先试032不在区号表里就试03如果在就归类为国内长途。我最初实现时把国家代码和区号放在同一张表里查导致这类号码分类错误。正确做法是严格区分两张表区分标准就是“是否以 00 开头”。5.6 输出“Unknown”时的区号显示网上常见的输出格式里对于不可识别号码会在 50 字符区域内输出原始号码后面跟Unknown字样费用写 0。不同版本可能显示Unrecognized或其他字符串。这里没有统一标准以题目样例为准。6. 性能分析与优化心得6.1 数据规模评估费率表行数不多通常只有几十条到几百条。呼叫记录可能很多但总数也在合理范围内。用map做前缀查找每次查找代价 O(log N)完全够用。6.2 是否需要预处理所有前缀因为我们按长度从长到短尝试匹配每次都要做substr构造子串。substr会复制字符串如果前缀很长、尝试次数很多会有轻微开销。但在这个数据量下完全无感不需要优化。如果你想写得高效一点可以用string::compare代替substr但可读性会变差。实际更值得花时间优化的地方是输入输出。如果你的实现用的是cin/cout建议加上ios::sync_with_stdio(false); cin.tie(nullptr);这一步能让 IO 快不少。虽然本题数据量不大不加也能过但养成习惯没坏处。6.3 推荐的重构思路如果你的代码写完了但很乱我建议你按这个顺序重构把费率表读取、号码解析、分类判定、计费、输出分别拆成独立函数。分类函数只负责返回一个结构体包含类别、区号、国家代码、本地号码。计费函数只接收分类结果和时长返回费用。输出函数单独负责格式化。这样拆完之后每一部分都可以独立验证。我调试这道题时把分类结果单独打印出来过一遍比直接调整个流程快得多。7. 从这道题延伸出去的东西7.1 前缀匹配问题的一般化思路UVa 139 的核心是“最长前缀匹配优先”这个思想在很多场景里都能见到。比如 IP 地址路由表的最长前缀匹配、字典树自动补全、号码归属地查询系统本质上都是“给定一串数字/字符找到最长的已知前缀”。如果你把这道题做透了以后遇到类似需求第一反应就会是“从长到短试”而不是暴力遍历所有可能。7.2 业务规则枚举的工程价值在真实系统里“计费规则”往往是一张数据库表而不是硬编码。写这道题时那种“分类靠 if-else 堆叠、每条规则都要验证边界”的感觉和实际开发里对接计费需求非常像。你锻炼出的不是某个算法而是一种“把业务文档变成可靠代码”的能力。这道题里分类和计费两条链路是清晰的但在实际项目中你还需要考虑并发、日志、异常回滚等比这复杂得多。7.3 做题之外的收获如果非要我总结一个最值得记住的经验那就是当一道模拟题看起来很简单时细节就是全部。UVa 139 没有高深的算法它的难度全部藏在“读入格式”“前缀长度”“向上取整”“输出对齐”这些不起眼的地方。做完之后你再遇到类似的文本处理题目就会有一种“也不过如此”的底气。我自己前几天重新翻出这道题重温时发现当年写的代码还有不少可以精简的地方。比如分类逻辑和费率查找可以合并成一种“状态机”写法而不是三个 if 块。但说实话对于竞赛场景来说代码是否精美不是第一位的正确性和清晰度才是。如果你只是为了通过用最直白的方式写反而更不容易出错。最后再分享一个小技巧这题的测试数据建议你多构造几个“边界记录”比如空号、只含区号没有本地号、国际号码国家代码不存在、区号不存在、时长恰好 60 秒、时长 61 秒等。把这些 case 跑一遍能帮你省下很多次无意义的提交。编程题最怕的不是不会做而是自己以为会做了交给机器才发现还有一堆没考虑到的情况。UVa 139 会帮你练出这种“凡事多想一步”的习惯。