CF1348C Phoenix and Distribution

Phoenix 有一个由小写拉丁字母组成的字符串 $s$。他想将字符串中的所有字母分配到 $k$ 个非空字符串 $a_1, a_2, \dots, a_k$ 中，使得 $s$ 的每个字母恰好属于一个 $a_i$。这些 $a_i$ 不需要是 $s$ 的子串。Phoenix 可以任意分配 $s$ 的字母，并且可以随意重排每个 $a_i$ 内部的字母。 例如，若 $s = $ baba 且 $k=2$，Phoenix 可以有多种分配方式，例如： - ba 和 ba - a 和 abb - ab 和 ab - aa 和 bb 但以下分配方式是无效的： - baa 和 ba - b 和 ba - baba 和空串（$a_i$ 必须非空） Phoenix 想要将 $s$ 的字母分配到 $k$ 个字符串 $a_1, a_2, \dots, a_k$ 中，使得这 $k$ 个字符串中字典序最大的字符串尽可能小，即最小化 $max(a_1, a_2, \dots, a_k)$。请你帮他找到最优分配方案，并输出 $max(a_1, a_2, \dots, a_k)$ 的最小可能值。 如果字符串 $x$ 是字符串 $y$ 的前缀且 $x \ne y$，或者存在某个下标 $i$（$1 \le i \le min(|x|, |y|)$），使得 $x_i < y_i$ 且对于所有 $j$（$1 \le j < i$）都有 $x_j = y_j$，则称字符串 $x$ 的字典序小于字符串 $y$。这里 $|x|$ 表示字符串 $x$ 的长度。

输入包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。每个测试用例包含两行。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 10^5$），分别表示字符串 $s$ 的长度和要分配的非空字符串的数量。 每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，仅由小写拉丁字母组成。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

输出 $t$ 行，每行一个答案。第 $i$ 行输出第 $i$ 个测试用例中 $max(a_1, a_2, \dots, a_k)$ 的最小可能值。

在第一个测试用例中，一种最优方案是将 baba 分配为 ab 和 ab。 在第二个测试用例中，一种最优方案是将 baacb 分配为 abbc 和 a。 在第三个测试用例中，一种最优方案是将 baacb 分配为 ac、ab 和 b。 在第四个测试用例中，一种最优方案是将 aaaaa 分配为 aa、aa 和 a。 在第五个测试用例中，一种最优方案是将 aaxxzz 分配为 az、az、x 和 x。 在第六个测试用例中，一种最优方案是将 phoenix 分配为 ehinopx。 由 ChatGPT 4.1 翻译