CF1497A Meximization 题解

Content

给定 \(n\) 个数 \(a_1,a_2,\dots,a_n\)，你需要将这些数重新排列，使得 \(\sum\limits_{i=1}^n\operatorname{mex}(a_1,a_2,\dots,a_i)\) 最大。

数据范围：\(1\leqslant t\leqslant 100\)，\(1\leqslant n\leqslant 100\)，\(0\leqslant a_i\leqslant 100\)。

Solution

不难发现，如果我们将一个在原数列中已有的数放进去，那么 \(\operatorname{mex}\) 值必定是不变的。所以，我们将所有数不重复地从小到大放入新数列中，再将原来没选进去的数按任意顺序放在最后，可以证明这样放的 \(\operatorname{mex}\) 值最大。

Code

int a[107];int main() {
MT {
int n = Rint, vis[107] = {0}, tmp[107] = {0};
F(i, 1, n) a[i] = Rint;
sort(a + 1, a + n + 1);
F(i, 1, n) {
if(!vis[a[i]]) write(a[i]), putchar(' '), vis[a[i]] = 1;
else tmp[++tmp[0]] = a[i];
}
F(i, 1, tmp[0]) write(tmp[i]), putchar(' ');
puts("");
}
return 0;
}