题目理解

我们有一个长度为 $n$ 的数组 $a$ 和一个整数 $x$。每次操作可以选择一个元素将其增加 $x$（可以多次对同一元素操作）。目标是最大化数组的 MEX（最小缺失非负整数）。

核心观察：

• 要使 MEX 至少为 $k$，必须保证 $0,1,\dots,k-1$ 每个数在数组中都至少出现一次。
• 由于只有 $n$ 个元素，MEX 最大不会超过 $n$（因为要覆盖 $0$ 到 $n-1$ 需要 $n$ 个不同的数）。
• 我们只能增加元素的值，不能减小。因此初始值大于 $n$ 的元素对构建 $0$ 到 $n-1$ 没有帮助，可以忽略。

解题思路

1. 频率统计

建立频率数组 $freq$，其中 $freq[v]$ 表示值为 $v$ 的元素个数。我们只关心 $0$ 到 $n$ 的范围（因为 MEX 不会超过 $n$）。

2. 贪心策略

从 $k = 0$ 开始，依次检查每个数是否出现：

• 如果 $freq[k] > 0$：说明 $k$ 已经存在，我们可以尝试让 MEX 更大。此时如果 $freq[k] > 1$（有重复），我们可以保留一个 $k$，把多余的 $freq[k]-1$ 个元素通过若干次 $+x$ 操作变成更大的数。由于每次只能加 $x$，这些元素可以变成 $k+x, k+2x, k+3x, \dots$。我们把这些元素计入对应的频率中：$freq[k+x] \mathrel{+}= freq[k]-1$。然后将 $freq[k]$ 设为 $1$（只保留一个）。

• 如果 $freq[k] = 0$：说明 $k$ 无法被凑出来，此时 MEX 最大就是 $k$，停止循环。

3. 为什么这样是对的？

• 我们从小到大处理，保证每个数 $k$ 在需要时已经存在（要么初始就有，要么由之前的重复元素通过加 $x$ 得到）。
• 当遇到 $freq[k] = 0$ 时，没有任何办法得到 $k$（因为只能加 $x$，无法减，而所有小于 $k$ 的数都已经处理完毕，不会再有新元素变成 $k$）。
• 重复元素提前“升级”到更大的数，为后面可能缺失的数做准备。

4. 时间复杂度

每个测试用例 $O(n)$，因为只遍历 $0$ 到 $n$ 一次，并且每个元素至多被“移动”一次到更大的位置。

示例解析

示例 1

$n=6, x=3, a=[0,3,2,1,5,2]$

频率统计（只考虑 $0$ 到 $6$）： $freq[0]=1, freq[1]=1, freq[2]=2, freq[3]=1, freq[4]=0, freq[5]=1, freq[6]=0$

过程：

• $k=0$：$freq[0]=1>0$，$freq[0]=1$ 无重复 → 继续。
• $k=1$：$freq[1]=1>0$，无重复 → 继续。
• $k=2$：$freq[2]=2>0$，有重复。保留 $1$ 个 $2$，把 $1$ 个 $2$ 变成 $2+3=5$ → $freq[5]=1+1=2$，$freq[2]=1$。现在 $freq[5]=2$。
• $k=3$：$freq[3]=1>0$，无重复 → 继续。
• $k=4$：$freq[4]=0$ → 停止。MEX $=4$。

示例 2

$n=6, x=2, a=[1,3,4,1,0,2]$

频率统计（$0$ 到 $6$）： $freq[0]=1, freq[1]=2, freq[2]=1, freq[3]=1, freq[4]=1, freq[5]=0, freq[6]=0$

过程：

• $k=0$：$freq[0]=1$ → 继续。
• $k=1$：$freq[1]=2>0$，有重复。保留 $1$ 个 $1$，把 $1$ 个 $1$ 变成 $1+2=3$ → $freq[3]=1+1=2$，$freq[1]=1$。
• $k=2$：$freq[2]=1$ → 继续。
• $k=3$：$freq[3]=2>0$，有重复。保留 $1$ 个 $3$，把 $1$ 个 $3$ 变成 $3+2=5$ → $freq[5]=0+1=1$，$freq[3]=1$。
• $k=4$：$freq[4]=1$ → 继续。
• $k=5$：$freq[5]=1>0$，无重复 → 继续。
• $k=6$：$freq[6]=0$ → 停止。MEX $=6$。

示例 3

$n=4, x=5, a=[2,5,10,3]$

频率统计（$0$ 到 $4$）： $freq[0]=0, freq[1]=0, freq[2]=1, freq[3]=1, freq[4]=0$

过程：

• $k=0$：$freq[0]=0$ → 停止。MEX $=0$。

代码实现要点

def solve():
    t = int(input())
    for _ in range(t):
        n, x = map(int, input().split())
        a = list(map(int, input().split()))
        
        freq = [0] * (n + 1)  # 只关心 0 到 n
        for val in a:
            if val <= n:
                freq[val] += 1
        
        for k in range(n + 1):
            if freq[k] == 0:
                print(k)
                break
            if freq[k] > 1 and k + x <= n:
                freq[k + x] += freq[k] - 1
                freq[k] = 1

注意：当 $k+x > n$ 时，多余的重复元素无法帮助构建 $0$ 到 $n$ 范围内的数，可以丢弃（因为对提高 MEX 无贡献）。