308304: CF1497A. Meximization
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Meximization
题意翻译
给定 $n$ 个数 $a_1,a_2,\dots,a_n$,你需要将这些数重新排列,使得 $\sum\limits_{i=1}^n\operatorname{mex}(a_1,a_2,\dots,a_i)$ 最大。 $\operatorname{mex}$ 求的是在一组数中没有出现过的**最小非负整数**,例如 $\operatorname{mex}(\{1,2,3\})=0$,$\operatorname{mex}(\{0,1,2,4,5\})=3$。 $t$ 组数据,$1\leqslant t\leqslant 100$,$1\leqslant n\leqslant 100$,$0\leqslant a_i\leqslant 100$。 Translated by Eason_AC 2021.3.20题目描述
You are given an integer $ n $ and an array $ a_1, a_2, \ldots, a_n $ . You should reorder the elements of the array $ a $ in such way that the sum of $ \textbf{MEX} $ on prefixes ( $ i $ -th prefix is $ a_1, a_2, \ldots, a_i $ ) is maximized. Formally, you should find an array $ b_1, b_2, \ldots, b_n $ , such that the sets of elements of arrays $ a $ and $ b $ are equal (it is equivalent to array $ b $ can be found as an array $ a $ with some reordering of its elements) and $ \sum\limits_{i=1}^{n} \textbf{MEX}(b_1, b_2, \ldots, b_i) $ is maximized. $ \textbf{MEX} $ of a set of nonnegative integers is the minimal nonnegative integer such that it is not in the set. For example, $ \textbf{MEX}(\{1, 2, 3\}) = 0 $ , $ \textbf{MEX}(\{0, 1, 2, 4, 5\}) = 3 $ .输入输出格式
输入格式
The first line contains a single integer $ t $ $ (1 \le t \le 100) $ — the number of test cases. The first line of each test case contains a single integer $ n $ $ (1 \le n \le 100) $ . The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ $ (0 \le a_i \le 100) $ .
输出格式
For each test case print an array $ b_1, b_2, \ldots, b_n $ — the optimal reordering of $ a_1, a_2, \ldots, a_n $ , so the sum of $ \textbf{MEX} $ on its prefixes is maximized. If there exist multiple optimal answers you can find any.
输入输出样例
输入样例 #1
3
7
4 2 0 1 3 3 7
5
2 2 8 6 9
1
0
输出样例 #1
0 1 2 3 4 7 3
2 6 8 9 2
0