C. Phoenix and Distribution(贪心&字符串)

题目传送门

算法：贪心

题意：将长度为的字符串分成个子序列(每个字母只使用一次)，将字典序最大的子序列最小化。

思路：显然可以对字符串进行排序后再分配，根据贪心思想，每个子序列尽可能占用少的字典序小的字母。

于是有 ：

​

​ 对于情况，若,显然是平均分配最好，否则将其全部分配给是最优的。

此种情况显然是最好的。

此种情况显然是最优的。

AC代码：

#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm> 
using namespace std;
int main(){
    int t,n,k;
    cin>>t;
    while(t--){
        int n,k;
        string s;
        cin>>n>>k>>s;
        sort(s.begin(),s.end());
        if(s[0]!=s[k-1]){ //pos1
            cout<<s[k-1]<<endl;
            continue;
        }
        cout<<s[0];
        if(s[k]!=s[n-1]) //pos2 
            for(int i=k;i<n;i++) cout<<s[i];
        else  cout<<s.substr(k,(n-1)/k);
        cout<<endl;
    }
}