电话计费模拟：Trie最长前缀匹配与跨天计费避坑

电话计费模拟题这类题，我在带新人练手的时候见过太多次——题面人畜无害，读进去也就三五行：给你一张价目表，再给你一堆通话记录，把总账算出来。真动手写，卡住的人十有八九栽在两件事上：最长前缀匹配怎么写才不出错，跨天计费怎么把时间段切干净。这两块单独看都不算难，凑到一道题里，就变成一台专门生产 WA 的机器。

先把话说在前面，这篇东西不是给你贴一份能直接交的答案。我想讲的是这道题背后的决策链条：为什么老手第一反应是建 Trie 而不是排序二分，为什么时间一定要先统一成秒，为什么金额在中间过程绝不能碰浮点，为什么"接通费"看起来最不起眼却最容易扣分。这些判断你可能在别的题解里看不到，因为题解只贴结果,不讲它当初为什么这么选。

适合读这篇的人：正在刷 OJ 上计费类模拟题的、想搞明白 Trie 除背模板之外还能干嘛的、以及手头有个"按规则算钱"的真实需求（比如内部结算脚本）需要一个可靠骨架的。代码用的是标准 C++，不带任何第三方库，拿过去改改字段就能用。

1. 把题目模型拆干净：输入究竟在约束什么

1.1 一份典型题面的字段清单

这类题的价目表通常长这样：给若干条规则，每条规则包含一个号码前缀、一个每分钟单价，有的还会带一个接通费（也叫起步价、单次附加费）。通话记录则是若干行，每行给一个主叫号码、一个开始时刻、一个结束时刻，时刻精确到秒或者精确到分。

第一眼看过去平平无奇，但每一个字段背后都藏着一个必须明确的语义问题，而这些问题题面往往只用半句话带过。我把常见的问法列一下，你对照自己手上的题面逐条确认：

我最常看到的一种误读是把"最长前缀匹配"理解成"最先匹配上的那条规则"。这两者只在规则前缀互不包含时才等价。一旦你同时定义了1010和10108两条规则，号码1010800该走哪条，就是两种完全不同的答案。

1.2 三道关卡的难度排序

把这道题拆开，我会这样排难度：跨天切分 > 计费精度 > 最长前缀匹配。

很多人直觉上觉得 Trie 最难，其实 Trie 是这三块里最机械、最不容易写错的——结构固定，插入和查询的逻辑也就十几行。真正烧脑子的是时间轴切分，因为它涉及"日界线"和"费率时段边界"两层嵌套的切割，任何一层边界处理错一位，结果就飘了。而计费精度属于那种"写的时候没感觉，跑起来才发现差 1 分"的类型，它不难，但极其考验你有没有在动手前就想清楚。

顺带说一句，如果你时间紧，我建议的做题顺序是反过来的：先把 Trie 写完并单独测通，再写时间切分，最后处理金额。因为 Trie 的问题能通过打印中间结果立刻定位，而时间切分的问题往往要跑到最后输出才暴露，排在后面写你有足够的心理准备。

1.3 动手之前先手推三组数据

我在实际做题时有个习惯：读完题先不写代码，拿纸推三组数据，推完再开工。这三组数据的选取是有讲究的。

第一组推规则前缀互相包含的场景。比如定义1010单价 20 分、10108单价 12 分，号码10108000应该命中后者。推一遍你就知道查询时不能"命中即返回"，必须"一直往下走，边走边记"。

第二组推跨天的场景。23:50:00 打到次日 00:10:00，一共二十分钟，其中前十分钟在折扣时段、后十分钟在标准时段——前提是你的费率表确实是按一天内的时段划分的。如果整张表是全天统一价，那跨天只是日期变了，费率没变，切分反而简单。

第三组推不足一个计价单位的场景。比如每段只有 40 秒，按分钟向上取整就是 1 分钟。这一步推不通，后面所有代码都是白写。

推完这三组，你对整个模型的边界就有了手感，代码结构自然浮出来了。

2. 最长前缀匹配：暴力比较为什么会翻车

2.1 朴素解法的复杂度陷阱

最直觉的写法是：对每一通电话，遍历所有规则，判断号码是否以规则前缀开头，从所有命中的规则里挑最长的那个。

// 最直觉但不够好的写法 int best = -1, bestLen = -1; for (int i = 0; i < rules.size(); ++i) { if (number.compare(0, rules[i].prefix.size(), rules[i].prefix) == 0) { if ((int)rules[i].prefix.size() > bestLen) { bestLen = rules[i].prefix.size(); best = i; } } }

这段代码本身是对的，逻辑也清晰。问题在复杂度：假设规则 R 条、通话 N 条、号码平均长度 L，总代价是 O(N·R·L)。日常规模下这点开销根本不算什么，但它有两个隐藏麻烦。

一是规则数可能远超你的预期。有些题会给出几万条规则、几万条通话，这时候 O(N·R) 就变成了十亿级别的字符比较，跑不过时限。二是这种写法没法自然处理"前缀重复定义"。如果两条规则前缀完全相同但费率不同，是按后出现的覆盖前面的，还是按题面某些特殊约定，你需要额外加一层判断，代码会越改越乱。

Trie 恰好把这两个问题一起解决了：查询代价只和号码长度有关，与规则数量无关；重复前缀的覆盖问题，在插入时天然就是"后写覆盖"。

2.2 Trie 的节点设计：只存有用的东西

节点里放什么，这个设计决定了后面代码好不好改。我推荐的字段组合是这样：

struct TrieNode { int child[128]; // 用字符做下标，号码里有 '+' '-' 也不怕 long long centPerMin; // 每分钱数，-1 表示该前缀没有对应规则 long long connectFee; // 接通费，单位也是分 TrieNode() : centPerMin(-1), connectFee(0) { std::fill(child, child + 128, -1); } };

几个设计取舍值得说一下。

用int child[128]而不是int child[10]。电话号码理论上是数字，但真实场景里常带+、-、空格，甚至字母（比如某些虚拟号段）。用 128 个槽位覆盖全部 ASCII，代码不用做任何字符映射，128 × 4 字节 = 512 字节一个节点，规则几千条也很轻松。如果坚持用 10 个槽位，你就得写一个atoi式的映射函数，映射写错反而引入新 bug。

价格字段用long long存"分"，而不是double存"元"。这一点后面第 4 节展开讲，这里先记住结论：凡是涉及钱，内部一律整数。

用一个哨兵值-1标记"该节点不是规则终点"。这是整个设计的核心。因为 Trie 的中间节点和终点节点在结构上是一样的，你不加标记就分不清"这里确实有规则"和"这里只是路径上的一个中转"。哨兵值选-1而不是0，因为0是一个合法的费率（免费通话），用它当哨兵会把免费规则判成无效规则。

2.3 插入与查询的完整实现

插入就是顺着字符往下走，走不通就开新节点，走到头把费率写在当前节点上。注意最后一句是赋值不是追加，这样天然实现"后写覆盖"。

void insert(const std::string& prefix, long long centPerMin, long long connectFee) { int cur = 0; // 0 是虚拟根，不代表任何字符 for (char ch : prefix) { int c = (unsigned char)ch; if (nodes[cur].child[c] == -1) { nodes[cur].child[c] = (int)nodes.size(); nodes.emplace_back(); } cur = nodes[cur].child[c]; } nodes[cur].centPerMin = centPerMin; nodes[cur].connectFee = connectFee; }

查询的关键是边走边记。走到走不动为止，一路上最后一个"有费率"的节点就是答案。

struct MatchResult { bool found; long long centPerMin; long long connectFee; }; MatchResult query(const std::string& number) { int cur = 0; MatchResult res{false, 0, 0}; for (char ch : number) { int c = (unsigned char)ch; if (nodes[cur].child[c] == -1) break; // 走不动了，立刻停 cur = nodes[cur].child[c]; if (nodes[cur].centPerMin >= 0) { // 这个前缀有规则，先记下来 res.found = true; res.centPerMin = nodes[cur].centPerMin; res.connectFee = nodes[cur].connectFee; } } return res; }

这段代码里有三个细节，每一个都是踩过坑之后加上去的。

第一，break之后不 resetcur，因为res里已经存好了最后一个有效节点。如果你习惯性地写return {true, nodes[cur]...}，那就退化成"必须完全匹配才有效"，号码后面多几位就全废了。

第二，判断条件写>= 0而不是!= -1。看起来一样，但>= 0的语义是"这是一个合法费率"，而!= -1的语义是"这不是哨兵"，一旦你以后想用别的哨兵值（比如-2表示禁用规则），前者不用改。

第三，空号码要单独处理。上面这段代码对空串会直接返回found = false，因为循环一次都不执行。这通常是对的，但如果题面允许空前缀作为"默认规则"，你就得在循环前先检查根节点的费率。

2.4 排序加二分：另一种能落地的路线

Trie 不是唯一解。另一种我认为同样值得掌握的写法是：把所有规则按前缀字符串字典序排序，查询时用二分找"第一个大于等于号码的规则"，然后往回退几位检查是否构成前缀。

思路是这样的：字典序排序后，如果一个字符串 S 是号码 N 的前缀，那么 S 在排序数组中的位置一定在 N 附近——具体说，所有 S 的候选者都聚集在lower_bound(N)之前。你从lower_bound的位置往回退，检查N.compare(0, len, rule) == 0，找到的第一个就是最长前缀（因为排在前面的字符串更短或者字典序更小，实际需要往回扫多少位取决于你设定的最大前缀长度）。

这种写法在实战中的优势是代码短、无额外结构、易调试，你可以在调试器里直接看数组内容。劣势是往回扫的步数不容易界定，如果最大前缀长度是 20，你就得往回退 20 位，这 20 个邻居里可能有几十条规则，反而比 Trie 慢。

我的取舍是：规则数大于 1000 且查询量也大，用 Trie；规则数很少或者你就是想快速写个对拍程序，用排序二分。对拍程序用笨办法是最好的，因为它和主程序走的是完全不同的代码路径，错的地方很难撞车。

3. 跨天计费：把一条时间轴切成互不重叠的段

3.1 第一步永远是统一成秒

时间处理上我有一条铁律：只要涉及时间运算，先全部转成秒，算完再转回去。不要在HH:MM:SS格式上做加减，那是给自己找麻烦。

int toSec(int h, int m, int s) { return h * 3600 + m * 60 + s; }

转成秒之后，"跨天"这件事就变成了纯粹的数值比较：如果endSec <= startSec，说明结束时刻在次日甚至更晚，那么endSec += 86400。

这里要提醒一个容易被忽略的边界：endSec == startSec到底算零时长还是算跨满一天？这两个答案在现实里都有合理性，取决于题面。我在没有明确说明时倾向于算跨天（因为零时长的通话记录在业务上没有意义），但一定要在代码里用注释标出来，方便后面调整。

更麻烦的是通话超过一天的情况。有些题会给出 23:00 打到后天 01:00 这种数据。如果你的代码只判断一次if (end < start) end += 86400;，那 25 小时的时长会被算成 1 小时。稳妥的写法是用一个循环：

while (endSec <= startSec) endSec += 86400;

但这样遇到"零时长"会变成 24 小时，所以更稳的做法是先明确语义再写。我个人的习惯是把两种语义都实现成可切换的一行，用一个const bool kZeroMeansFullDay = false;之类的开关控制，调试时来回切。

3.2 按自然日切分，再按费率时段切分

跨天计费的本质是两层切割：第一层切自然日，第二层在每个自然日内部切费率时段。这个顺序不能颠倒，先切时段再切日会把边界搞乱。

第一层的写法很固定：

const long long DAY = 86400; long long cur = startSec; while (cur < endSec) { long long dayStart = cur - (cur % DAY); long long dayEnd = dayStart + DAY; long long segEnd = std::min(endSec, dayEnd); // 现在 [cur, segEnd) 落在同一个自然日内 processWithinDay(cur - dayStart, segEnd - dayStart, cents); cur = segEnd; }

cur - (cur % DAY)是求当天零点的经典写法，对非负整数永远成立。如果你的秒数可能为负（一般不会），要换成floor语义的写法。

注意while (cur < endSec)这个条件，它同时防住了两个坑：零长度段不会进入循环（避免死循环），跨多天会自动迭代多轮（不用额外判断）。

第二层是在processWithinDay里面，把"当天第几秒到第几秒"这段区间，拿去和费率时段表求交集。时段表我一般这么定义：

struct Bucket { int begin; // 当天第几秒（含） int end; // 当天第几秒（不含） long long centPerMin; };

然后求交集就三行：

for (const auto& b : buckets) { int lo = std::max(daySecBegin, b.begin); int hi = std::min(daySecEnd, b.end); if (lo >= hi) continue; // [lo, hi) 这段落在时段 b 内 }

这个双重循环的结构，比"预计算 86400 个秒各自的费率然后线性扫描"要通用得多，因为它不依赖日长固定，也不依赖时段必须有规律。时段数量一般不会超过十几个，性能完全够。

3.3 时段表的构建与边界对齐

构建时段表时最容易犯的错是区间开闭不一致。有人写[begin, end]有人写[begin, end)，两种混用就一定会在边界那一秒上重复计费或者漏计费。

我的建议是全程统一使用左闭右开[begin, end)。理由有三：一是它与 C++ 迭代器习惯一致，不容易写错；二是多段拼接时天然无缝（前一段的end就是后一段的begin）；三是"一天"这个整体区间可以自然表示为[0, 86400)，不用特殊处理最后一秒。

按左闭右开定义，假设折扣时段是 00:00 到 07:00，标准时段是 07:00 到 24:00，那么表格就是：

25200 就是 7 × 3600。这样定义之后，07:00:00 这一秒属于标准时段，06:59:59 属于折扣时段，不会有歧义。

还有一个隐蔽的坑：如果题面给的费率表本身有空洞怎么办？比如只定义了 08:00-18:00 的费率，其余时间没提。这种情况必须在读题阶段就弄清楚，因为代码里如果直接跳过未覆盖的秒数，那段时长就变成免费了，而且不报错，你很难发现。稳妥的做法是加一个断言或者日志，在调试模式下把未覆盖的区间打印出来。

3.4 接通费为什么只能收一次

这是我认为整道题里最容易被忽略、扣分最狠的一个点。

接通费的业务含义是"这通电话接通的成本"，它跟通话时长无关，跟通话次数有关。一通从 23:50 打到次日 00:10 的电话，无论你在内部把它切成了多少段、跨了几个费率时段、跨了几个自然日，接通费都只能收一次。

但代码结构天然会诱导你收多次，因为最自然的写法是在"每段计费"的函数里顺手加上接通费。我见过太多人这么写，然后在跨天用例上多收了钱。

正确的结构是：接通费在整通电话的最外层加一次，切分函数里只处理时长费用。

long long charge = match.connectFee; // 只在这里加一次 long long cents = 0; long long cur = startSec; while (cur < endSec) { ... cents += timeCostOfSegment(...); // 这里只算时长 cur = segEnd; } charge += cents;

如果你不确定题面到底要求哪种，去看示例数据。示例里只要有一条跨天的通话，你就能反推出接通费的正确口径——这是我在没有把握时最常用的验证手段，比反复读题面快得多。

4. 计费精度与聚合：钱这个东西不能拿 double 乱算

4.1 用整数分做内部计算

看到"每分钟 0.15 元"这种输入，很多人的第一反应是double rate = 0.15;，然后一路乘下去。这条路在金额小、通话短的测试点上完全正确，一到大规模数据就开始飘。

原因很简单：0.15在二进制浮点里根本没有精确表示，它存储的是0.1499999999999999944...。你乘 60 秒，误差被放大 60 倍。如果还要跨几段累加，误差继续叠加。最后输出时你printf("%.2f")，四舍五入的结果就可能偏一个最小单位——而 OJ 判题通常要求精确到分，差一分就是 WA。

我的做法是：读入时立刻把金额转成"分"的整数，全程用long long运算，只在最后输出时转回元。

读入这一步要小心。如果输入是"0.15"这种字符串，直接stod再乘 100 会引入浮点误差。更稳的方式是把字符串按小数点拆开，手工拼整数：

long long parseCent(const std::string& s) { size_t dot = s.find('.'); if (dot == std::string::npos) return std::stoll(s) * 100; std::string intPart = s.substr(0, dot); std::string fracPart = s.substr(dot + 1); while (fracPart.size() < 2) fracPart += '0'; // 补齐到两位 if (fracPart.size() > 2) fracPart = fracPart.substr(0, 2); // 多余位数直接截 return std::stoll(intPart) * 100 + std::stoll(fracPart); }

这段代码看着笨，但它把一个可能出错的浮点运算换成了两次数整数运算，确定性拉满。如果你确定输入格式固定是两位小数，甚至可以更粗暴：直接删掉小数点当整数读。

4.2 段内不足一分钟怎么算

这里有个必须说清楚的细节：按分钟计费时，"不足一分钟"是在哪个层级取整？

假设一通电话跨了两个费率段，第一段 40 秒、第二段 20 秒，两段单价不同。

• 方案 A：每段独立向上取整。第一段算 1 分钟，第二段算 1 分钟，总时长按 2 分钟计费。
• 方案 B：全程先加总为 60 秒，再向上取整为 1 分钟，然后按段拆分比例。
• 方案 C：全程按秒精确累计，最后统一向上取整到分钟。

三种方案出来的钱完全不同。方案 A 最符合"每个费率时段单独结算"的业务直觉，也是大多数题面的口径；方案 C 最精确，但和"按分钟计费"的字面意思不符。

我的做法是：默认采用方案 A，但把这个选择写成一个显式的函数，方便改口径。具体实现是在段内先算出秒数，再按需要向上取整：

// 段内计费：secs 是这段的秒数，centPerMin 是每分钟价格（分） long long segCost(long long secs, long long centPerMin, bool roundUpPerSeg) { if (roundUpPerSeg) { long long minutes = (secs + 59) / 60; // 向上取整到分钟 return minutes * centPerMin; } return secs * centPerMin / 60; // 按秒精确折算，向下取整 }

如果你用的是按秒精确折算的方案，还有一层优化：把分子累加起来，最后统一除一次。因为secs * centPerMin / 60每次除法都会截断误差，段数一多误差就累积了。改成先累加secs * centPerMin得到总分子，最后再(numerator + 30) / 60做四舍五入，误差就从"每段一次"降到"每通一次"。

long long numerator = 0; // 单位是"分·秒" // 循环内： numerator += secs * centPerMin; // 循环外： long long timeCost = (numerator + 30) / 60; // 四舍五入

加 30 是因为除数是 60，加上除数的一半就实现了四舍五入。这个技巧在我处理所有整数除法场景时都适用，值得记住。

4.3 汇总与输出格式

最后一步是把每通电话的金额汇总输出。这里有一个常被忽略的问题：取整是在每通电话结束时做，还是所有电话汇总后做一次？

如果题面要求"逐个输出每通电话的费用"，那显然在每通内部取整。如果只要求"输出总费用"，那就要看题面怎么描述。选错了，误差会随通话数量线性放大。

我的默认选择是：在每通电话内部完成取整，然后整数相加得总额。这样每通电话的金额是独立可验证的，出了问题能定位到具体哪条记录，调试效率高很多。

输出格式方面，printf("%lld.%02lld\n", cent / 100, cent % 100)是最稳的写法，比printf("%.2f", cent / 100.0)更可靠——后者又把整数拉回浮点了，没有必要。注意负数情况，如果可能出现退款金额，/和%对负数的行为是向零取整，要先取绝对值再拼符号。

5. 调试实录：那几次让我半夜改代码的 WA

5.1 一组必须自己造的边界用例

OJ 给的样例通常只覆盖主路径，边界全靠自己造。我每次做这类题都会固定跑下面这张清单，跑全通过再交。

我把这张表存在本地一个edge_cases.txt里，做同类题的时候直接拿过来改。这个习惯帮我省下的时间，比我认真读十遍题面加起来还多。

5.2 用暴力解对拍

当我不确定自己的优化写法哪里出错时，我用的是最原始的办法：写一份暴力解，随机生成数据，两者逐条比对。

暴力解的思路极其笨拙——时间精确到秒逐秒模拟，每一秒去查一遍规则，用最简单的字符串比较找最长前缀。它慢，但它的正确性几乎不需要证明。

// 暴力版：逐秒模拟 long long bruteForce(...) { long long cost = connectFee; for (long long t = startSec; t < endSec; ++t) { int secOfDay = t % 86400; long long rate = -1; for (auto& r : rules) { if (number.compare(0, r.prefix.size(), r.prefix) == 0) { if (rate < 0 || r.prefix.size() > ...) rate = r.centPerMin; } } // 按 secOfDay 查时段，累加这一秒的费用 } }

生成随机数据的时候有个技巧：不要均匀随机，要刻意制造极端值。前缀故意互相包含、时间故意贴着时段边界、号码长度故意拉满。均匀随机的数据十次有九次测不出问题，你把边界密度调高，往往跑十组就能炸出 bug。

对拍跑通之后我的信心会高很多，因为两条完全不同的实现路径同时正确的概率，比单一实现高得多。

5.3 常见判错原因对照表

最后整理一份我这些年在这类题上踩过的坑，按出现频率排序。

我个人体会最深的是"金额差一分"那一行。它教我养成一个习惯：凡是涉及钱的代码，动手前先想清楚单位，写的时候一次成型，绝不留"先跑起来再说"的余地。因为这类错误在调试时几乎无法定位——你看着一堆数字，不知道自己错在哪一分。

还有一个不是技术但很实用的经验：把 Trie、时段切分、金额计算三块写成三个独立函数，每块单独写个小main测通再拼起来。拼装的时候如果结果不对，你至少知道问题一定出在拼装层，而不是"三块里某一块有 bug"。这个拆分习惯在时限紧张的时候特别值钱，它把定位问题从"大海捞针"变成了"逐块排除"。

最后再分享一个小技巧。如果题目的费率表比较复杂，我会在调试模式下把每条通话的明细打出来：命中了哪条前缀、切成了几段、每段多少秒、每段多少钱、接通费多少、合计多少。这份明细在本地跑一遍，跟手推的结果对一遍，心里就有底了。真正提交之前把输出关掉，不影响最终结果。