\(n\) 本书必须分成 \(k\) 部分在书架（\(k \mid n\)），每本书用一个小写的拉丁字母 \([a, y]\) 表示。每部分必须有严格 \(\frac{n}{k}\) 本书。
当所有书分配完成后，对于每个部分编号为 \(1, 2, \cdots, k\) ，每部分的有 \(\frac{n}{k}\) 本书，他们的 \(MEX\) 表示这个部分，作为代表字符。希望从 \(1\) 至 \(k\) 部分的代表字符构成的字符串字典序最大。
输出这个代表字符。
贪心的结合：字典序思维结合 \(MEX\) 思维。
先按字典序思维考虑，从 \(1\) 到 \(k\) 考虑。希望 越前面得到的字符 字典序越大。
假设当前位置为 \(i\) ，再按 \(MEX\) 思维考虑。希望当前的 \(MXE\) 尽可能大。即能够连续得到的字符尽可能多。
我们直接从贡献角度考虑。统计出 \(cnt_0 \sim cnt_{25}\) 。
遍历 \(1 \sim k\) 个部分。对于每个部分，存在 \(\frac{n}{k}\) 个字符，即连续字符串最后一个的取值可能为 \(0 \sim \frac{n}{k} - 1\) ，在这个区域枚举。
- 用指针 \(j\) 在 \(0 \sim \frac{n}{k} - 1\) 从小到大枚举字符，连续放入。\(cnt_j--\) 。
- 当出现 \(cnt_j = 0\) ，即连续中断。可以确定此时 \(mex = j\) 。枚举可以结束。
- 提前结束导致后一段空余的空间，在整体程序结束后可以随意填入，不影响结果。
- 所有字符都可以连续出现，则 \(mex = \frac{n}{k}\) ，不妨初始化成它。
view
#include <bits/stdc++.h>
void solve() {
int n, k; std::cin >> n >> k;
int cnt[26] = {0};
std::string str; std::cin >> str;
for (int i = 0; i < n; i++) cnt[str[i] - 'a'] += 1;
std::string ans = "";
for (int i = 1; i <= k; i++) {
int mex = n / k;
for (int j = 0; j < n / k; j++) {
if (cnt[j] > 0) cnt[j]--;
else { mex = j; break; }
}
ans += (char)('a' + mex);
}
std::cout << ans << '\n';
}
signed main() {
int _ = 1; std::cin >> _;
while (_--) solve();
return 0;
}