CF1497A Meximization 题解

2024-10-16 16:35:16

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;

}

最新文章

热门文章