最小修改次数使数列子串 mex 避开指定值

给定一个长度为 n 的数列 a 和一个整数 k，求最少修改多少个元素，使得数列 a 的任意连续子串的 mex 都不等于 k。

*本题中，数列的 mex 被定义为数列中最小未出现的自然数，例如：

mex'1,2,3'=0，因为 0 是自然数。 mex'0,1,3'=2。 mex'0,1,2'=3。

算法思路：

使用一个栈 st 来维护当前子串的 mex，遍历数列，对于每个元素 a[i]，如果 a[i] 等于 k，则清空栈，否则将 a[i] 入栈。每次入栈后，计算当前栈的 mex，并更新最小修改次数。

C++ 代码：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100005;

int n, k, a[N], st[N], top;

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int ans = n;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == k) top = 0;
        else st[++top] = a[i];
        int mex = 0;
        while (mex <= top && st[mex+1] == mex) mex++;
        ans = min(ans, i - mex);
    }
    cout << ans << endl;
    return 0;
}

代码解析：

定义数组 a 来存储数列，栈 st 用于维护当前子串的 mex，top 指向栈顶，ans 记录最小修改次数。
遍历数列 a，对于每个元素 a[i]：
- 如果 a[i] 等于 k，则清空栈，因为 k 是需要避免的值，所以当前子串的 mex 无法确定。
- 否则将 a[i] 入栈。
计算当前栈的 mex：
- 从 0 开始，依次检查栈中是否有元素等于 mex。
- 如果有，则 mex++，继续检查下一个元素。
- 当 mex 大于栈顶元素，或检查完所有元素，则当前栈的 mex 就是 mex。
更新最小修改次数：
- 当前子串的最小修改次数为 i - mex，因为只需要修改栈中 mex 之前的元素即可。
- 将 ans 更新为当前最小修改次数和之前最小修改次数的较小值。
最后输出 ans，即最小修改次数。