题解：P7697 [COCI2009-2010#4] OGRADA

来看一下这道题。

第一问

容易想到把所有面积减去涂了的面积。

那如何计算呢？

这似乎是“滑动窗口”的例题。

显然，每块区域涂的面积，就是这块高度的最小值再乘上 k。

这个东西，明显可用单调队列维护。

可是把所有的加起来，却有重复的情况。

看图：

设前一个高度为 last，当前高度为 now，t 为 last 与 now 之间的最小值，则重叠部分就为 t 与 (k-1) 的积。

得到这个，跑一遍即可。

第二问

我们不是得到了要刷的面积吗？

直接扫一遍，如果这块不等于前面那块，或者刷子不够刷时，计数器加一。

代码

需要私信我。