P3254. 补种未成活胡杨

解题思路

不定滑窗解法

一种非常容易想到的做法是，对原来给定的数据进行平铺还原的操作。譬如对于示例二：

我们将这个长度为 10 的原数组平铺为：

其中 0 表示尚未种树，1 表示已经种树。

> 注意，由于题目所给定的编号是 1-N，而数组的下标是从 0 开始的，此处的编号会存在一个 1 的偏差。

这部分过程的代码如下：

由于 k = 1，这意味着我们只能够最多种下一棵树。种下的这棵树，要使得数组存在 最长的连续的 1。

所以问题就可以转变为：找到一个最长的连续子数组，这个子数组包含 k 个 0。因为这 k 个 0 都将会被替换为 1，将得到最长的连续 1 的个数。

譬如对于示例二而言，我们仅需将索引为 6 的未成活杨树进行补种，就可以得到最长的连续 1 的数组：

直接使用 滑窗三问三答 就很简单了：

注意到上述做法的时间复杂度是 O(N) 的，当 N 取上限值 10^5 时，是可以通过所有用例的。

---

固定滑窗解法

固定滑窗的解法较抽象，但是时间复杂度可以达到更加优秀的 O(M) 的复杂度。感兴趣的同学可以自行学习。

从题目所给的几个例子可以看出，如果 M 远小于 N，那么那些原先已经连续成活的树木，完全可以只用区间长度来进行表示。

譬如对于示例二，由于我们知道为未成活的杨树编号分别为：

那么也就知道，原先就已经成活的杨树被分成了 4 部分（4 个区间），其中数目分别为：

这样就比不定滑窗解法中，将原先的数组进行平铺出来的这种做法：

进行了 更进一步的数据压缩。

这个结果可以用下面代码得到：

其中 tree_left 表示，某个未成活杨树编号的左边，一共存在多少棵连续的活树。同理 tree_right 表示，某个未成活杨树编号的右边，一共存在多少棵连续的活树。

譬如对于上述例子存在：

由于每种下一棵树，能够使得每一个死树的左右两边的连续活树连接起来。因此我们会考虑，如果将其中原先的 M 棵死树中的近邻的 K 棵进行种植，则可以尽可能长地得到连续的活树了。

这就退化成了一个 固定滑窗 的问题。

考虑原来的长度为 M 的死树数组 trees，选择其中连续的 K 个元素将其转为活树，使得连续的活树数目尽可能的多。求最大的连续活树的数目。

显然，每一个固定滑窗中连续存活的活树数目由三部分构成：

• 这 K 棵补种的活树
• 这 K 棵补种的活树中的最左边那棵补种的树，其左边连续的活树数目
• 这 K 棵补种的活树的每一棵树，其右边连续的活树数目

因此第一个固定滑窗的初始化为：

而每一次窗口移动的时候，最右边新补种的树的右边，要将加上 tree_right[right] 棵新种下的树。（A1） 而最左边原先补种的树不再种植，那么这部分原先存在窗口中的树 tree_left[left] 将被删去。（A2）

考虑 固定滑窗三问三答，代码为：