UVa 145 这个编号老玩家一看就知道是经典模拟题题名叫 Gondwanaland Telecom——一个虚构国家的电信公司。题面不长规则也很朴素一天分成白天、傍晚、深夜三个时段每个时段每分钟价格不同通话按距离分成五个计费档位每个档位对应不同的三时段价格表。你要做的就是把每条通话记录拆成三个时段各占多少分钟再乘价格、求和、按格式输出。听起来像是给小学生出的应用题但它在评测机上挂过的次数多得惊人。原因很简单通话可能跨午夜边界分钟可能被重复计算输出列宽差一个空格都算错价格单位从分换成元还有人会漏掉。这些坑和算法复杂度没关系和“你是不是把真实规则翻译成了严谨的代码”有直接关系。这篇文章我从题意讲到两套实现再讲评测机和真实计费系统里的门道适合所有准备在模拟题上少交几次学费的人。1. 这道题到底在考什么1.1 虚构电话公司的三段式计价规则Gondwanaland 是题面虚构的地名整套电话系统也是虚构的但规则非常贴近真实运营商的思路。一天 24 小时被切成三段白天08:00 - 18:00傍晚18:00 - 22:00深夜22:00 - 次日 08:00三个时段分别有每分钟的资费。除此之外通话还会根据距离远近分成 5 个计费档位题面用 A 到 E 五个字母表示。每个档位在三个时段的价格不一样所以价格本质上是张二维表横向是时段纵向是档位。输入的前 5 行就是这张表。表之后跟着一条条通话记录每条记录包含四个字段计费档位字母、电话号码、开始时间、通话时长。开始时间一般是 HHMM 格式的整数比如 2345 表示 23 点 45 分时长以分钟为单位。遇到以#开头的行为止所有输入结束。举个例子一条记录写成A 1234567890 2345 30含义就是“档位 A号码 123456789023:45 开始通话 30 分钟”。有些版本的题面字段顺序可能略有差异写代码前先确认你手上这道题的 Input 段怎么说别想当然。1.2 明明只是模拟为什么一堆人 WA这道题没有高级算法不需要贪心不需要动态规划甚至连排序都用不上。它真正考察的是三件细活第一能不能把时间区间拆清楚。三个时段的边界是 08:00、18:00、22:00 这三个整点其中 18:00 和 22:00 最容易被写错差一个等号边界那一分钟就会被算进两个时段。第二能不能处理跨午夜。电话不会乖乖只在当天打23:30 开始打 90 分钟结束就是次日 01:00。如果只盯着start i这一个时间轴深夜后半段全部漏算。第三能不能按题目要求精确格式化输出。老在线评测系统对输出空格非常敏感列宽不对就是 Wrong Answer本地跑得再漂亮也没用。这三件事都不是智力挑战而是工程里面的“细心挑战”。这类应用模拟题存在的意义就是模拟真实业务里的脏活细活让你提前体会一下“需求一句话细节坑死人”的感觉。1.3 做这题需要的最小知识清单别被题面吓到前置知识非常少会用scanf或cin读字符串和整数会用printf控制输出宽度理解取模运算%会开一个二维数组存价格表。就这些。不需要 map不需要高精度不需要任何高级数据结构。正因为门槛低它经常被放在训练计划的前面用来帮新手建立“把现实规则转成代码”的信心。2. 先把一天抽象成 1440 分钟2.1 HHMM 到分钟所有时间计算的第一步时间计算最忌讳直接拿“小时”和“分钟”分开算因为进位、借位很容易出错。统一做法是把 HHMM 转成从 00:00 开始算的分钟数。假如你读进来的开始时间是一个整数startTime那么hh startTime / 100; mm startTime % 100; start hh * 60 mm;比如 0800 读进来是整数 800800 / 100 8800 % 100 0所以start 480。比如 2345 读进来是 23452345 / 100 232345 % 100 45所以start 23 * 60 45 1425。这一步做完后面所有区间判断都变成纯整数比较清爽很多。2.2 三个时段的左闭右开区间用左闭右开区间把三个时段写成数学形式白天 Day[480, 1080)即 08:00 ≤ t 18:00傍晚 Evening[1080, 1320)即 18:00 ≤ t 22:00深夜 Night[1320, 1440) 以及 [0, 480)即 22:00 ≤ t 或 t 08:00为什么要坚持左闭右开因为闭区间会把边界分钟重复算。比如一个通话从 18:00 开始如果白天写成[480, 1080]傍晚也写成[1080, 1320]那 1080 这一分钟同时属于白天和傍晚总时长凭空多出一分钟。现实里一个时刻只能属于一个时段代码里就必须用和把界限卡死。我个人的习惯是凡是时间段一律写成[start, end)判断时用判断起点、用判断终点从根上杜绝重复计数。2.3 跨午夜通话把时间轴变成环跨午夜是这个题的第一个大坑。假设通话从 23:30 开始持续 90 分钟结束于次日 01:00。如果直接按线性时间轴算前 30 分钟落在 1425 到 1440 之间后 60 分钟落在 1440 到 1515 之间而后面的 1440、1500 这些数已经超出了“一天”的范围硬塞进 Day、Evening 区间里什么都匹配不上。解决办法是取模t (start i) % 1440。% 1440 会把时间轴首尾相接1440 变成 01441 变成 1这样次日 00:00 到 01:00 就被自动映射回当天凌晨的 0 到 60 分钟正好落进深夜时段的[0, 480)区间。一行取模跨午夜问题直接消失这是逐分钟模拟方案里最漂亮的一笔。2.4 价格表怎么存二维数组的下标顺序价格表是[档位][时段]还是[时段][档位]看起来无所谓实际踩坑的人不在少数。我建议固定成price[5][3]第一维是档位第二维是时段。读表的时候第 i 行第 j 个数就存进price[i][j]。后面算账时先用记录里的档位字母算出step stepStr[0] - A再拿price[step][0]、price[step][1]、price[step][2]分别对应白天、傍晚、深夜的价格。下标顺序一旦写反结果就是档位和时段串位样例可能碰巧对隐藏数据一跑就崩。3. 两种实现逐分钟模拟与 O(1) 区间重叠3.1 方案一逐分钟模拟稳字当头最直观的思路是把通话的每一分钟都拆出来判断它属于哪个时段累加分钟数。代码很短逻辑清晰几乎不会算错。#include cstdio int price[5][3]; int getPeriod(int t) { if (t 480 t 1080) return 0; // Day if (t 1080 t 1320) return 1; // Evening return 2; // Night } int main() { for (int i 0; i 5; i) { for (int j 0; j 3; j) { scanf(%d, price[i][j]); } } char stepStr[8], number[16]; int startTime, duration; while (scanf(%s, stepStr) 1 stepStr[0] ! #) { scanf(%s%d%d, number, startTime, duration); int start (startTime / 100) * 60 (startTime % 100); int minutes[3] {0, 0, 0}; for (int i 0; i duration; i) { int t (start i) % 1440; minutes[getPeriod(t)]; } int step stepStr[0] - A; int total minutes[0] * price[step][0] minutes[1] * price[step][1] minutes[2] * price[step][2]; printf(%10s%6d%6d%6d%8.2f\n, number, minutes[0], minutes[1], minutes[2], total / 100.0); } return 0; }这段代码的核心就是第 17 行的(start i) % 1440。每一分钟都单独查一次时段哪怕通话时长有一千分钟也就循环一千次对这种数据量完全没压力。价格我按整数“分”存算完的总价也是分输出时再除以 100 转成“元”。用整数能躲开浮点累积误差最后一步交给%.2f处理小数。提示如果你担心电话号码有前导零用字符串读就对了。输出时直接%s打回去前导零不会丢。3.2 方案二区间重叠公式O(1) 算出结果逐分钟模拟在题目范围内没问题但如果你把自己代入真实场景要处理几十万条通话记录每分钟循环显然不合适。更工程化的做法是直接算两个区间重叠了多少分钟。先写一个最基础的函数给两个左闭右开区间[a, b)和[c, d)返回重叠长度。int overlap(int a, int b, int c, int d) { int left a c ? a : c; int right b d ? b : d; return right left ? right - left : 0; }原理很简单重叠区间的左端点是两个左端点的较大值右端点是两个右端点的较小值如果右端点没有超过左端点说明没有重叠返回 0。然后对每个时段分别调用这个函数统计白天、傍晚、深夜各有多少分钟落在通话区间内。深夜区间本身是断开的要拆成[1320, 1440)和[0, 480)两段分别统计。3.3 跨午夜场景的完整计算到这里还差一步跨午夜怎么办。思路是给每个时段准备一份“镜像区间”把它整体往未来平移 1440 分钟。因为单条通话时长不会超过一天所以只要原始区间加一份日后的镜像就能覆盖所有跨午夜的情况。写成代码是这样#include cstdio #include algorithm using namespace std; int price[5][3]; int overlap(int a, int b, int c, int d) { int left max(a, c); int right min(b, d); return max(0, right - left); } int countInSegment(int start, int end, int segStart, int segEnd) { int cnt overlap(start, end, segStart, segEnd); if (end 1440) { cnt overlap(start, end, segStart 1440, segEnd 1440); } return cnt; } int main() { for (int i 0; i 5; i) { for (int j 0; j 3; j) { scanf(%d, price[i][j]); } } char stepStr[8], number[16]; int startTime, duration; while (scanf(%s, stepStr) 1 stepStr[0] ! #) { scanf(%s%d%d, number, startTime, duration); int start (startTime / 100) * 60 (startTime % 100); int end start duration; int day countInSegment(start, end, 480, 1080); int eve countInSegment(start, end, 1080, 1320); int night countInSegment(start, end, 1320, 1440) countInSegment(start, end, 0, 480); int step stepStr[0] - A; int total day * price[step][0] eve * price[step][1] night * price[step][2]; printf(%10s%6d%6d%6d%8.2f\n, number, day, eve, night, total / 100.0); } return 0; }验证一下 23:30 打 90 分钟的例子start 是 1425end 是 1515。白天、傍晚都是 0深夜第一段[1320, 1440)和[1425, 1515)重叠出 15 分钟深夜第二段的镜像[1440, 1920)和[1425, 1515)重叠出 75 分钟总共 90 分钟全部是深夜。结果和逐分钟模拟完全一致。注意如果某条通话时长超过 1440 分钟等于跨了不止一天。先把完整的天数按“每天 600 分钟白天、240 分钟傍晚、600 分钟深夜”提前算掉剩下的不足一天的部分再用这套重叠逻辑。本题不会出现那么长的通话但把这个思路记下来做真实计费系统时一定用得上。3.4 两种方案怎么选比较项逐分钟模拟区间重叠理解成本低逻辑直观中需要理解镜像区间跨午夜处理% 1440一句搞定要复制一份日后的区间单条复杂度O(duration)O(1)出错点几乎没有镜像区间容易漏边界容易飘适合场景本题、快速 AC大量数据处理、工程实现我的建议比赛里优先选逐分钟模拟省心且不容易写错练习时把区间重叠也写一遍把它当成“时间区间重叠”的通用模板记住。这个模板以后做日历排期、资源占用统计、视频切片时长分配都能复用性价比很高。4. 输入输出与评测机的隐形规则4.1 记录怎么读、在哪里停老式在线评测系统的输入习惯是前面若干行是配置后面逐行是数据用特殊标记或文件尾结束。本题用#开头表示结束。用scanf(%s, stepStr)读第一个字段然后判断stepStr[0] ! #决定是否继续。符号化读入会自动跳过空格和换行所以不用担心空行问题也不用自己写复杂的行解析。电话号码强烈建议按字符串读。就算它看起来是纯数字字符串也能保留前导零输出时原样打回。你要是图省事读成 int万一数据里出现001234这种号码你就永远把它打不回来了。4.2 输出列宽最容易忽略的 WA 来源这种老题对输出格式的挑剔程度远超你的想象。它要求每一列右对齐空格数量必须严格一致你多一个空格或者少一个空格都会被判定为错误。本地跑起来看着挺整齐不代表评测机认账。我习惯用printf(%10s%6d%6d%6d%8.2f\n, ...)这种方式号码右对齐占 10 列三个分钟数各占 6 列总价占 8 列保留两位小数。具体列宽以你手上题面的 Output 段为准我只强调一个原则先数清楚列宽再写代码别拿样例格式去猜。4.3 用整数分算钱最后再转元如果价格表里有小数很多人第一反应是用 double 存。但 0.1 0.2 不等于 0.3 这种经典问题会在累计很多次之后给你一个莫名其妙的偏差。更稳的做法是价格按“分”存成整数总费用也用整数分累加最后输出前再除以 100.0 转成元。这样中间过程全是整数运算不会有精度问题。输出端用printf的%.2f负责进位即可不要自己额外做四舍五入画蛇添足容易出错。提醒单位换算是新手重灾区。输入价格是“分/分钟”输出总价是“元”中间差一个 100 倍。你要是忘了最后那一步除法样例可能因为数值恰好能整除而通过隐藏数据就一片红。4.4 WA 高频原因速查表症状可能原因处理办法深夜通话算出来为 0start i没取模改成(start i) % 1440通话总分钟数比输入的时长多边界分钟被算进两个时段统一左闭右开区间数字对了但格式错输出列宽不符按题面 Output 段逐列数空格总费用差一点零头单位搞错或浮点累积用整数分计算最后除 100程序停不下来结束标记没判断判断#同时兼容 EOF前面价格表全读串二维数组下标顺序反了固定用[档位][时段]5. 从 UVa 145 看真实计费系统的门道5.1 玩具版和工业版差在哪真正做过通信计费的人看到这题会会心一笑这就是计费引擎里最核心的“时段累加”那一小步。真实的计费系统里复杂度至少还要再乘上好几倍更多时段工作日、周末、节假日各自有独立的忙时闲时表更细的计费单位按秒计费或者按 6 秒脉冲进位套餐抵扣先扣免费分钟数再对剩余量计费多级阶梯同一个时段里用量超过某个阈值后单价变化舍入规则总价四舍五入到分、到角或者按电信运营商的特殊舍入约定。但万变不离其宗底层都是“把时间切成若干段按不同单价求和”这个模型。UVa 145 相当于把这个模型最核心的一小块抽出来让你用最短的代码亲手实现一遍。把这道题吃透以后再遇到复杂的计费规则至少不会慌。5.2 可迁移到其他领域的区间思维这种区间重叠的技巧不只属于电话计费。云服务器的按量计费、CDN 流量的分时段价格、机房的分时电价全是同一套逻辑。再往外走日历排班、会议室预约、停车场时段收费判断两个时间段是否重叠、重叠多久用的还是那个overlap函数。所以我始终觉得模拟题的价值被很多人低估了——它训练的不是“写 if-else”而是把真实世界的规则翻译成严谨的区间与条件这种翻译能力在任何业务系统里都是硬通货。6. 复盘心得三次 WA 教会我的事6.1 我的排错现场我第一次交这道题连吃三发 WA。第一发是没取模深夜时段全错第二发是 18:00 的边界用成了闭区间同时 18:00 这一分钟被白天和傍晚各算了一次总时长多出一分钟而且输出列宽少了一个空格两个问题叠在一起第三发是价格表下标顺序写成了[时段][档位]隐藏数据一跑档位和时段全串位。三次 WA 没有一次是算法不会全是“想当然”。从那次之后我给自己定了几条规矩。第一凡是涉及时间的题一律先转成分钟区间一律写左闭右开第二写完主逻辑先用边界用例自测23:59、00:00、08:00、18:00、22:00 各打一分钟能过这些基本就稳了第三输出格式永远先看题面 Output 段不靠样例猜。这几条规矩后来帮我避开了大量模拟题里的坑不只是这一道。6.2 一个值得做的变形练习如果你已经把这题 AC我强烈建议你多花半小时做一次变形把三个时段改成从配置里动态读入时段数量不固定价格表也由输入给出然后试着用区间重叠法写一个通用版本。你会发现overlap函数完全不用改只要把每个时段的起止时间存进数组循环求和就行。再进一步把计费单位从分钟改成秒输入格式变成 HH:MM:SS看看哪里会变复杂。我做这个变形题是在一次无聊的周末本来只想验证一下自己的理解结果意外发现那段通用代码后来直接被我拿去改成了一个小工具用来算会议室按时间段收费的账单。所以说UVa 145 不难但它值得你多花一点时间把“会 AC”变成“会设计”。那一次变形练习带给我的收获比反复刷十道熟悉题型都大。