C++ / ACM 自学笔记 · v5.0

(十四) 从推导到程序职责与错误定位

写代码前,把每项规则对应到一份状态、一个判断或一次更新。这样出错时能沿着对应关系定位,而不是对整个程序重新猜算法。

推导中的一句话 数对程序中的职责 窗口程序中的职责
已经处理过的对象是什么 frequency 只保存过去位置 两个堆保存窗口状态
当前对象需要什么信息 查 K-x 的过去次数 查空闲编号或最早完成时刻
当前步骤计算了什么 加入以当前位置为较后端的新数对 确定当前顾客的开始时刻与窗口
更新后留给下一步什么 把 x 的频次增加 1 把窗口转为忙碌,now 保存本次开始时刻
最终怎样输出 累计数对数量 每位安排、总等待、最大等待

1. 通过第一处不同定位更新次序

数对题读到 [3]、目标 6 时,正确过程为“查询 3 的次数 0,答案不变,再写入 3”。如果先写入,再查询,就会得到一对,第一步已经与合法下标要求不同。

下面是错误写法,用来定位问题;它是循环内部的演示片段,不是答案程序:

++frequency[x]; // 错误:先写入,查询时已经能看见当前位置。
auto it = frequency.find(target - x);
if (it != frequency.end()) {
    answer += it->second; // x+x==target 时,把当前项与自己配成一对。
}

同样的数据下,窗口题若把 finish<=now 写成 finish<now,时刻 2 完成的窗口就不能在时刻 2 接待顾客 3;偏差出在“结束时刻即可接待”的翻译。先比较时刻 2 的窗口集合,就能定位这个判断,而不必等到最后的总等待时间。

从输出偏差追到第一次状态差异和对应规则

2. 分开核对模型、算法与实现

“把任意选择当成连续区间”改写了合法方案,是模型错误;硬币题模型仍是最少枚数,但“先拿大硬币”漏掉更好的完整方案,是算法推导错误;数对的频次模型正确,却先写后查,是实现没有执行已经推导的顺序。

先手算失败输入的正确结果,再逐步记录自己的状态。若模型已经允许题目禁止的选择,应先改模型;若步骤理由不能解释某个合法方案,应补推导;若推导与手算一致而运行过程不同,就对照变量、分支和更新顺序修代码。

查阅笔记正文与全部题解 · Ctrl / ⌘ K