【深圳 IO 攻略】第 23 关：污染监测智能窗
本文首发于 B 站《深圳 IO》文集（https://www.bilibili.com/read/readlist/rl569860）。原创不易，转载请注明出处。
关卡展示
本关要求当（包括当前时间在内的）前 8 秒内，污染监测传感器的平均值大于等于 50 时关闭窗户，平均值小于 50 时开启窗户。题目保证前 7 秒的平均值不会大于等于 50。因此问题等价于：前 8 秒内的污染值总和大于等于 400 时关闭窗户，小于 400 时开启窗户。
初版方案：用 RAM 记录现在和过往的污染值，每一秒钟我们都统计前 8 秒的污染值总和是否小于 400，然后决定是否打开窗户就行了。由于 RAM 可以记 14 个数字，所以记住前 8 秒的污染值那是绰绰有余。电路图和代码如下：
首先我们将当前的污染值存入 RAM（mov p0 x0），然后准备开始统计前 8 秒的污染值总和。设当前 RAM 的指针地址是 a，则我们需要统计 a-8 ~ a-1 地址范围内的污染值总和。由于读取一次 RAM 后地址会自增，所以最终地址是 a-1+1 = a 自己。我们将最终地址 a 放入 dat 寄存器（mov x1 dat），然后将 RAM 的地址置为首地址 a-8，准备计算前 8 秒的污染值总和（mov x1 acc, sub 8, mov acc x1）。计算总和之前，我们需要将 acc 清零（mov 0 acc）。然后开始不断读 RAM，并将读到的值加到 acc 里（add x1）。每读一个值，都判定一次是否到达结束地址（teq x1 dat）。尚未到达结束地址时，跳回第 7 行继续累加（- jmp 7），直到读完前 8 秒的污染值后，计算这些污染值的总和是否小于 400（tlt acc 400）。小于 400 时打开窗户（+ mov 100 p1），否则关闭窗户（- mov 0 p1）。做完这些操作后，休眠一秒，进入下一个时钟周期（slp 1）。
点击左下角的【模拟】，稍等片刻，便会弹出结算界面：
利用【滑动窗口】算法提高运行效率
我们的初版算法达到了惊人的 1.5K 耗电量。这是因为我们在计算前 8 秒的污染值总和时涉及到了太多重复的计算。设 v(i) 为第 i 秒时的污染值，S(j, k) 为第 j~k 秒的污染值总和。那么，我们的初版算法里，是这样计算污染值总和的：
S(1, 8) = v(1) + v(2) + ... + v(8)
S(2, 9) = v(2) + v(3) + ... + v(9)
S(3, 10) = v(3) + v(4) + ... + v(10)
...
可以看到，每次都要读取 8 个数进行累加。如果我们使用动态计算的思维（下一个结果由上一个结果动态推导而出），就可以大大减少计算量：
S(1, 8) = v(1) + v(2) + ... + v(8)
S(2, 9) = S(1, 8) - v(1) + v(9)，无需重复计算 v(2) + v(3) + ... + v(8)
S(3, 10) = S(2, 9) - v(2) + v(10)，无需重复计算 v(3) + v(4) + ... + v(9)
...
可以看到，改进的算法里，下一秒的污染总和，只需要在上一秒的基础上减去一个值再加上一个值就可以了，只需要读两个数字。相比于初版方案，减少了大量重复计算，效率大大提升。这种通过移动左右边界，动态计算区间和的算法就叫做【滑动窗口】算法，简称【滑窗】算法。正好这道题也是个【滑窗】问题。
改进后的电路图和代码如下：
首先我们将右边界置为 8，左边界保持为 0，视为从第 8 秒开始统计，第 0~7 秒的污染值之和为 0（mov 8 x3）。每到达新的一秒，我们将 acc 的值减去原先左边界的值（sub x0），然后加上新值（add p0），并将新值存入原先的右边界所指向的空间（mov p0 x2）。操作完成后，左边界和右边界会各向右移动一格。此时我们便完成了一次【滑窗】计算，acc 的值为前 8 秒内的污染值总和。判断该值是否小于 400（tlt acc 400），小于 400 时打开窗户（+ mov 100 p1），否则关闭窗户（- mov 0 p1）。做完这些操作后，休眠一秒，进入下一个时钟周期（slp 1）。
点击左下角的【模拟】，稍等片刻，便会弹出结算界面：
电量由 1.5K 骤降到 277，代码行数也由 13 行降到 8 行，质的飞跃！
