很简单的题。虽然没在考场上做出来
分析
我们经过思考，容易得出以下结论：
- 如果当前 $mex = x$，则下一个删的数一定小于 $x$。
- 如果 $mex = 0$，那么我们就可以不往下算了，因为它们对答案的贡献为 $0$。
我们设 $f[i]$ 表示当 $mex = i$ 时，$m$ 的值。
则有：
$$f[i] = \min(f[j] + (c[i] - 1) \times j + i, f[i])$$
其中 $j > i$，$c[i]$ 表示 $i$ 在 $a$ 中的个数。
因为，我们要使 $mex = i$，就必须将 $i$ 这个数删去，并且 $0 \sim i-1$ 都还存在于 $a$ 中。我们会删 $c[i]$ 次，但 $c[i] - 1$ 次，$m$ 会加上上一个 $mex$ 的值。 第 $c[i]$ 次则会加上 $i$，也就是新的 $mex$。
设没删任何数的 $mex = first$。
根据定义，初始化 $f[first] = 0$。
根据上述结论，与定义，答案即为 $f[0]$。
Code
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
using namespace std;
const int N = 5e3 + 5;
int t, x, p;
ll c[N], f[N];
ll pre, now, n;
int main() {
ios::sync_with_stdio(0);
cin >> t;
while (t--) {
cin >> n;
ll mx = 0;
memset(c, 0, sizeof c);
memset(f, 0x3f, sizeof f);
for (int i = 1; i <= n; i++) {
ll x;
cin >> x;
if (x <= 5001) c[x]++, mx = max(mx, x);//因为至多 5000 个数，但数可能大于 5000。
}
for (int i = 0; i <= mx + 1; i++) {//找到没删任何数时的 mex。
if (!c[i]) {
p = i;
break;
}
}
f[p] = 0;
for (int i = p; i >= 0; i--) {
for (int j = i - 1; j >= 0; j--) {
f[j] = min(f[i] + (c[j] - 1) * i + j, f[j]);
}
}
cout << f[0] << '\n';
}
return 0;
}