A12218. Cutting Out
编程题
普及/提高-
知识点
题目描述
You are given an array $s$ consisting of $n$ integers.
You have to find any array $t$ of length $k$ such that you can cut out maximum number of copies of array $t$ from array $s$ .
Cutting out the copy of $t$ means that for each element $t_i$ of array $t$ you have to find $t_i$ in $s$ and remove it from $s$ . If for some $t_i$ you cannot find such element in $s$ , then you cannot cut out one more copy of $t$ . The both arrays can contain duplicate elements.
For example, if $s = [1, 2, 3, 2, 4, 3, 1]$ and $k = 3$ then one of the possible answers is $t = [1, 2, 3]$ . This array $t$ can be cut out $2$ times.
- To cut out the first copy of $t$ you can use the elements $[1, \underline{\textbf{2}}, 3, 2, 4, \underline{\textbf{3}}, \underline{\textbf{1}}]$ (use the highlighted elements). After cutting out the first copy of $t$ the array $s$ can look like $[1, 3, 2, 4]$ .
- To cut out the second copy of $t$ you can use the elements $[\underline{\textbf{1}}, \underline{\textbf{3}}, \underline{\textbf{2}}, 4]$ . After cutting out the second copy of $t$ the array $s$ will be $[4]$ .
Your task is to find such array $t$ that you can cut out the copy of $t$ from $s$ maximum number of times. If there are multiple answers, you may choose any of them.
You have to find any array $t$ of length $k$ such that you can cut out maximum number of copies of array $t$ from array $s$ .
Cutting out the copy of $t$ means that for each element $t_i$ of array $t$ you have to find $t_i$ in $s$ and remove it from $s$ . If for some $t_i$ you cannot find such element in $s$ , then you cannot cut out one more copy of $t$ . The both arrays can contain duplicate elements.
For example, if $s = [1, 2, 3, 2, 4, 3, 1]$ and $k = 3$ then one of the possible answers is $t = [1, 2, 3]$ . This array $t$ can be cut out $2$ times.
- To cut out the first copy of $t$ you can use the elements $[1, \underline{\textbf{2}}, 3, 2, 4, \underline{\textbf{3}}, \underline{\textbf{1}}]$ (use the highlighted elements). After cutting out the first copy of $t$ the array $s$ can look like $[1, 3, 2, 4]$ .
- To cut out the second copy of $t$ you can use the elements $[\underline{\textbf{1}}, \underline{\textbf{3}}, \underline{\textbf{2}}, 4]$ . After cutting out the second copy of $t$ the array $s$ will be $[4]$ .
Your task is to find such array $t$ that you can cut out the copy of $t$ from $s$ maximum number of times. If there are multiple answers, you may choose any of them.
输入格式
The first line of the input contains two integers $n$ and $k$ ( $1 \le k \le n \le 2 \cdot 10^5$ ) — the number of elements in $s$ and the desired number of elements in $t$ , respectively.
The second line of the input contains exactly $n$ integers $s_1, s_2, \dots, s_n$ ( $1 \le s_i \le 2 \cdot 10^5$ ).
The second line of the input contains exactly $n$ integers $s_1, s_2, \dots, s_n$ ( $1 \le s_i \le 2 \cdot 10^5$ ).
输出格式
Print $k$ integers — the elements of array $t$ such that you can cut out maximum possible number of copies of this array from $s$ . If there are multiple answers, print any of them. The required array $t$ can contain duplicate elements. All the elements of $t$ ( $t_1, t_2, \dots, t_k$ ) should satisfy the following condition: $1 \le t_i \le 2 \cdot 10^5$ .
输入输出样例
输入 #1
7 3 1 2 3 2 4 3 1
输出 #1
1 2 3
输入 #2
10 4 1 3 1 3 10 3 7 7 12 3
输出 #2
7 3 1 3
输入 #3
15 2 1 2 1 1 1 2 1 1 2 1 2 1 1 1 1
输出 #3
1 1
说明/提示
The first example is described in the problem statement.
In the second example the only answer is $[7, 3, 1, 3]$ and any its permutations. It can be shown that you cannot choose any other array such that the maximum number of copies you can cut out would be equal to $2$ .
In the third example the array $t$ can be cut out $5$ times.
In the second example the only answer is $[7, 3, 1, 3]$ and any its permutations. It can be shown that you cannot choose any other array such that the maximum number of copies you can cut out would be equal to $2$ .
In the third example the array $t$ can be cut out $5$ times.