Phoenix has a string ss consisting of lowercase Latin letters. He wants to distribute all the letters of his string into kk non-empty strings a1,a2,…,aka1,a2,…,ak such that every letter of ss goes to exactly one of the strings aiai . The strings aiai do not need to be substrings of ss . Phoenix can distribute letters of ss and rearrange the letters within each string aiai however he wants.
For example, if s=s= baba and k=2k=2 , Phoenix may distribute the letters of his string in many ways, such as:
- ba and ba
- a and abb
- ab and ab
- aa and bb
But these ways are invalid:
- baa and ba
- b and ba
- baba and empty string (aiai should be non-empty)
Phoenix wants to distribute the letters of his string ss into kk strings a1,a2,…,aka1,a2,…,ak to minimize the lexicographically maximum string among them, i. e. minimize max(a1,a2,…,ak)max(a1,a2,…,ak) . Help him find the optimal distribution and print the minimal possible value of max(a1,a2,…,ak)max(a1,a2,…,ak) .
String xx is lexicographically less than string yy if either xx is a prefix of yy and x≠yx≠y , or there exists an index ii (1≤i≤min(|x|,|y|))1≤i≤min(|x|,|y|)) such that xixi < yiyi and for every jj (1≤j<i)(1≤j<i) xj=yjxj=yj . Here |x||x| denotes the length of the string xx .
The input consists of multiple test cases. The first line contains an integer tt (1≤t≤10001≤t≤1000 ) — the number of test cases. Each test case consists of two lines.
The first line of each test case consists of two integers nn and kk (1≤k≤n≤1051≤k≤n≤105 ) — the length of string ss and the number of non-empty strings, into which Phoenix wants to distribute letters of ss , respectively.
The second line of each test case contains a string ss of length nn consisting only of lowercase Latin letters.
It is guaranteed that the sum of nn over all test cases is ≤105≤105 .
Print tt answers — one per test case. The ii -th answer should be the minimal possible value of max(a1,a2,…,ak)max(a1,a2,…,ak) in the ii -th test case.
6 4 2 baba 5 2 baacb 5 3 baacb 5 3 aaaaa 6 4 aaxxzz 7 1 phoenix
ab abbc b aa x ehinopx
大意就是给一个字符串，可以把字母顺序打乱，然后用这些字母构造k个串使得字典序最大的字符串的字典序最小。
首先可以想到，因为这k个串非空，所以都必然有一个首字母，把原字符串从小到大sort后的第k个字母一定是最终造出来的字典序最大的字符串的首字母。然后这么看，假设第k个字母是x，如果第1~k-1里没有x或者不全是x的话，直接输出一个x即可，因为可以把剩下的所有字母都填到最小的字母后面，构成类似ayyyzzz b c d ... x这样，x的字典序大于ayyyzzz；如果1~k个字母全是x的话，考虑第k+1到第n个字母，如果这些字母全部相同的话，则平均分到每个字符串，如果不全部相同，则把剩下的字母全部添加到一个x的后面（假设不全部添加到某个x后面的话，会发现不是最优情况，比如wxyz和w以及wyz和wx，肯定是前者更优）。
#include <bits/stdc++.h> using namespace std; char s[100005]; int n,k,i; int main() { int t; cin>>t; while(t--) { cin>>n>>k; scanf("%s",s); vector<char>v; sort(s,s+n); v.push_back(s[k-1]); int cnt=1; if(k==1) { cout<<s<<endl; continue; } for(i=0;i<n;i++) { if(i<k-1&&s[i]==s[k-1])cnt++; } bool flag=1; for(i=k;i<n;i++) { if(s[i]!=s[k])flag=0; } if(cnt!=k)//剩下的全给最小的那个 { cout<<s[k-1]<<endl; continue; } else { if(!flag) { for(i=k;i<n;i++)v.push_back(s[i]); } else { int res=(n-k)%k; for(i=1;i<=(n-k)/k;i++)v.push_back(s[k]); if(res)v.push_back(s[k]); } } for(i=0;i<v.size();i++) { cout<<v[i]; } cout<<endl; } }