Cutting Out

题意翻译

#### 题目描述 给你一个序列 $s$，长度为 $n$. 你需要找到一个长度为 $k$ 的序列 $t$ 使得它能被最多次数地从 $s$ 中切割。 一次切割的意思是你需要对于 $t$ 序列中所有 $t_i$，在 $s$ 中找到一个跟它相同的数，并将其移除。 举例，如果 $s=[1,2,3,2,4,3,1]$，$k=3$，那么一种可行的方案是 $t=[1,2,3]$，这个子序列可以被切割两次。 - 第一次切割，你可以选择 $[1, \underline{\textbf{2}}, 3, 2, 4, \underline{\textbf{3}}, \underline{\textbf{1}}]$，移除完后 $s=[1,3,2,4]$； - 第二次切割，你可以选择 $s=[\underline{\textbf{1}},\underline{\textbf{3}},\underline{\textbf{2}},4]$，移除完后 $s=[4]$。 你的任务是找到一个序列 $t$，能最多次数地从 $s$ 中切割它。如果有多个可行的方案，只需输出任意一种。 #### 输入格式 第一行两个整数 $n,k(1\le k\le n\le 2\times 10^5)$，表示 $s$ 序列的长度和 $t$ 序列的长度。 接下来一行 $n$ 个整数 $s_1,s_2,...,s_n(1\le s_i\le 2\times 10^5)$。 #### 输出格式 输出 $k$ 个整数，表示你找到的序列 $t$ 使得能被切割的次数最大。如果有多个方案，只需输出任意一种。 #### 样例解释 第一个样例在样例描述中已经说过。 第二个样例中可行的方案只有 $[7,3,1,3]$ 和它的全排列。可以证明你不能找到其它长度为 $k$ 的序列 $t$ 使得能被切割两次 第三个样例中 $t=[1,1]$ 可以被切割五次。

题目描述

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.

输入输出格式

输入格式

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 $ ).

输出格式

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.