题解：滑动窗口最小值与木板涂刷优化

---

问题分析

本题要求用宽度为 $X$ 的滚筒刷涂栅栏，每次选择连续的 $X$ 块木板，只能涂到这些木板中最矮的高度。剩余部分需要用牙刷涂抹。需要求：

1. 牙刷涂抹的最小面积
2. 在满足面积最小的情况下，滚筒刷的最小使用次数

关键约束：

• 滚筒刷必须完全接触连续的 $X$ 块木板
• 滚筒刷只能涂到所选木板中的最小高度
• 可以多次使用滚筒刷，不同次之间可以有重叠

---

核心观察

1. 最优涂刷策略

对于每块木板 $i$，它能被滚筒刷涂到的最大高度等于：

• 以 $i$ 为起点的长度为 $X$ 的窗口中的最小高度
• 以 $i$ 为终点的长度为 $X$ 的窗口中的最小高度
• 取这两者的最大值

因为木板 $i$ 可能被包含在多个窗口（滚筒刷位置）中，且每个窗口都只能涂到窗口内木板的最小高度。

2. 最小牙刷面积

设 $h_i$ 表示木板 $i$ 能被滚筒刷涂到的最大高度，则：

• 必须用牙刷涂抹的面积 = $\sum_{i=1}^N (a_i - h_i)$
• 其中 $a_i$ 是木板 $i$ 的实际高度

因此，最小牙刷面积问题转化为：对每个位置 $i$，求出它能被滚筒刷涂到的最大高度 $h_i$。

---

算法框架

第一步：计算滑动窗口最小值

使用单调队列（双端队列）计算：

1. mini[i]：以位置 $i$ 结尾的长度为 $X$ 的窗口中的最小高度

   • 扩展数组 a[] 到长度 $n+X$，便于处理边界
   • 使用单调递增队列维护窗口最小值

2. 同样方法计算以位置 $i$ 开始（或以 $i-X+1$ 结尾）的窗口最小值

第二步：计算每个木板的最大可涂高度

对于木板 $i$，它能被滚筒刷涂到的最大高度 $h_i$ 等于：

• 以 $i$ 为起点的窗口最小值（即 mini[i+X-1]）
• 以 $i$ 为终点的窗口最小值（即 mini[i]）

但代码中采用更巧妙的方法：

1. 先计算所有以 $i$ 结尾的窗口最小值 mini[i]
2. 再对 mini[] 数组用大小为 $X$ 的滑动窗口求最大值，得到最终的 $h_i$

第三步：计算最小滚筒刷次数

在确定了 $h_i$ 后，需要找到最少的滚筒刷使用次数来覆盖所有高度为 $h_i$ 的区域。

关键观察：

• 如果连续的木板的 $h_i$ 相同，它们可以被同一个滚筒刷覆盖（可能需要多次）
• 对于长度为 $len$ 的连续相同 $h_i$ 区域，最少需要 $\lceil len / X \rceil$ 次滚筒刷

因此，统计所有连续的 $h_i$ 相同区间，对每个区间计算 $\lceil 长度 / X \rceil$ 并求和。

---

关键实现细节

单调队列

• 队列存储数组索引
• 维护队列单调性：新元素比队尾小时弹出队尾
• 维护窗口大小：队首元素超出窗口时弹出

边界处理

// 扩展数组边界
for (int i = 1; i <= n + x; i++) {
    // 处理滑动窗口最小值
}

// 填充边界值
fill(mini + 1, mini + x + 1, mini[x]);
fill(mini + n + 1, mini + n + x + 1, mini[n]);

滚筒刷次数计算

int len = 0;
for (int i = 1; i <= n; i++) {
    if (h[i] != h[i - 1]) {
        ans2 += (len - 1) / x + 1;  // ceil(len / x)
        len = 1;
    } else {
        len++;
    }
}
ans2 += (len - 1) / x + 1;  // 处理最后一段

---

复杂度分析

• 时间复杂度：$O(N)$
  • 两次单调队列扫描：$O(N)$
  • 统计连续区间：$O(N)$
• 空间复杂度：$O(N)$
  • 存储原数组和中间数组：$O(N)$

对于 $N \le 10^6$ 完全可行。

---

正确性证明

1. $h_i$ 的计算正确性

对于木板 $i$，它可能被包含在多个窗口中。它能被涂到的最大高度等于所有包含它的窗口的最小高度的最大值。

由于窗口是连续的长度为 $X$ 的区间，包含 $i$ 的窗口可以表示为：

• 以 $i$ 为右端点的窗口：$[i-X+1, i]$
• 以 $i$ 为左端点的窗口：$[i, i+X-1]$

这两个窗口的最小值的最大值确实覆盖了所有可能包含 $i$ 的窗口。

2. 滚筒刷次数最小性

由于滚筒刷一次只能覆盖连续的 $X$ 个位置，对于长度为 $len$ 的连续相同高度区域，至少需要 $\lceil len/X \rceil$ 次。且这个下界是可以达到的（例如从区域起点开始，每隔 $X$ 个位置刷一次）。

---

总结

本题是一道滑动窗口与单调队列的综合应用题，主要考察：

1. 问题转化能力：将涂刷问题转化为窗口最小值/最大值问题
2. 单调队列应用：高效计算滑动窗口最值
3. 边界处理技巧：处理数组边界和窗口越界
4. 贪心策略：计算最小滚筒刷使用次数

算法的核心技巧：

• 使用单调队列在 $O(N)$ 时间内计算所有滑动窗口最值
• 通过两次滑动窗口计算得到每个位置的最大可涂高度
• 利用连续区间长度计算最少滚筒刷次数

这种"两次单调队列+区间统计"的方法是解决此类窗口覆盖问题的有效范式，展示了如何将看似复杂的操作次数问题转化为简洁的数学计算。