P2537. 绘图机器

解题思路

题目理解

题目很难读，建议根据例子反推含义。 主要是对 绘制指令 `X offsetY` 的理解。

绘制指令 `X offsetY` 表示：在 x 轴的 X 位置，向 y 轴偏移 offsetY。 （注意：单词 offset 表示“偏移”的意思，所以绘制指令 X offsetY 表示一个 动作，而不是一个具体的坐标）

示例对应的图如下：

可以看出，线段和 x 轴围成的面积是： 1*1 + 1*2 + 1*3 + 6*1 = 12

解题思路

理解了题意之后，问题就比较简单了。

我们初始化当前点为原点 (cur_x, cur_y) = (0, 0)，且初始面积 area = 0。

如图所示，如果我们知道图中标注出来的点的坐标，就可以计算出所有的面积。

如果已知当前点的坐标 (cur_x, cur_y) 和指令 X offsetY，那么下一个点的坐标可以很方便地通过以下式子计算得到： (nxt_x, nxt_y) = (X, cur_y + offsetY) 而围成的面积的增量是： (nxt_x - cur_x) * cur_y

特别地，如果出现了直线位于 x 轴下方，那么面积需要取绝对值，即： abs((nxt_x - cur_x) * cur_y)

故单次更新面积的代码为：

复杂度分析 设 n 为绘制指令的条数。程序先用一个 for 循环读入 n 条指令存进 lst，这是 O(n)；再把终点 (E, -1) 追加到 lst 末尾，使最后一段水平线也能参与面积计算，追加是 O(1)。核心是那个遍历 n+1 个元素的 for 循环：每轮只做「算出下一个点坐标 (X, cur_y + offsetY)、把一块矩形面积 abs((nxt_x - cur_x) * cur_y) 累加进 area、更新当前点」三步常数操作，代码按输入顺序依次处理指令，没有嵌套循环，也不做排序，所以这一段是 O(n)。总时间复杂度为 O(n)，瓶颈就是这趟对指令列表的线性扫描。空间上，lst 完整存储了 n+1 条指令，空间复杂度为 O(n)，此外只用了 area、cur_x、cur_y 等常数个变量。