猫耳少女小 R 的数列游戏：Mex 优化问题

小 R 是一个可爱的猫耳女孩子，她喜欢研究数列的 mex。现在她有一个长度为 n 的数列 a。她讨厌整数 k，因此她希望修改数列 a 的若干个元素为任意自然数，使得 a 的任意连续子串的 mex 都不等于 k。

请你求出最少需要修改多少个元素。

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

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

代码实现

以下是 Python 3 的代码实现：

n, k = map(int, input().split())
a = list(map(int, input().split()))

ans = 0
for i in range(n):
    if a[i] == k:
        j = i
        while j < n and a[j] == k:
            j += 1
        length = j - i
        if i == 0 or j == n:
            ans += (length + 1) // 2
        else:
            ans += length // 2
        i = j - 1

print(ans)

代码思路

首先读入数列的长度 n 和不喜欢的数字 k，以及数列 a。

然后遍历数列 a，如果遇到了数字 k，则需要修改这个数字及其后面连续的数字，使得这个连续子串的 mex 不等于 k。具体来说，如果这个连续子串的长度是偶数，则只需要修改一半的数字，即连续子串中的奇数位置上的数字；如果这个连续子串的长度是奇数，则需要修改一半加一的数字，即连续子串中的偶数位置上的数字和最后一个数字。

最后输出修改的最小次数即可。