Codeforces Round #638 (Div. 2) C Phoenix and Distribution（思维/构造）
传送门
1.题目大意：给出一个字符串
s
s
s，现在需要将它的所有字符分成
k
k
k个非空字符串（不一定是它的子串），使得
k
k
k个字符串中字典序最大的最小
2.因为让最大的字典序最小，我们首先考虑第一个字符最小，那么先将源串从小到大排序，接着给 k k k个字符串各分配一个字符，这时不难发现，如果前 k k k小字符不相等的话， k + 1 k+1 k+1后面的所有字符都分配给最小字符的字符串，那么答案就是第 k k k个字符。但是如果前 k k k个都相等，那么再考虑 k + 1 k+1 k+1之后，因为我们已经升序处理，如果后面的存在不相等的字符，如果分配到多个 a a a字符串中，总会使某个串的某个位置变大，因此正确做法是将后面的都连到一个 a a a中；如果后面字符都相等，那么平均分配。最后还有一个特殊情况——最后一个样例， k k k为 1 1 1时直接输出排好序的 s s s
3.吐槽一波怎么这么多构造题，吐了
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;
string s;
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t,n,k;
cin>>t;
while(t--){
cin>>n>>k;
cin>>s;
sort(s.begin(),s.end());
if(k==1){
cout<<s<<endl;
continue;
}
if(s[k-1]!=s[0]){
cout<<s[k-1]<<endl;
continue;
}else{
int flag=0;
char c=s[k];
for(int i=k;i<s.size();i++){
if(s[i]!=c){
flag=1;
break;
}
}
if(flag){
for(int i=k-1;i<s.size();i++) cout<<s[i];
cout<<endl;
}else{
string ans="";
int len=(n-k)/k,num=(n-k)%k;
if(num) len++;
ans+=s[k-1];
for(int i=1;i<=len;i++) ans+=s[k];
cout<<ans<<endl;
}
}
}
return 0;
}