[ABC229D] Longest X 分析 & 双指针

__ryp__ · 2024-01-08 20:53:03 · 个人记录

本题是双指针问题。

我们可以将原序列以 k+1 个点为界，分为 A_i,\cdots,A_t。很明显，无论如何我们都不可能让两个 A 连成更大的连续 X 序列。然后我们的问题就转化为在这 t 个序列中替换 k 个点，找最终最大的结果。

我们维护快指针 p 与慢指针 q，p 始终指向当前序列的开头，而 q 进行遍历。我们在总替换的点数量不超过 k 的情况下，将看到的所有点全部替换为 X，直到末尾或者替换次数不够。此时答案就是 q - p。处理完之后，我们将 p 向右移动，找下一个点。

有一点细节：当原来的快指针指点时，我们需要将限制值减去一。同时，慢指针开始的时候指的是快指针前面一个单位。

双指针是考察细节与编码能力的算法。