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

题目传送门

算法：贪心

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

思路：显然可以对字符串进行排序后再分配，根据贪心思想，每个子序列 $s_i(i\in [1,k])$ 尽可能占用少的字典序小的字母。

于是有：

$pos1:if (str[0]!=str[k-1])\quad s_k=s[k-1]$

$pos2:if(str[0]==str[k-1])$

对于 $pos2$ 情况，若 $str[k]==s[n-1]$ ,显然是平均分配最好，否则将其全部分配给 $s_k$ 是最优的。

$ep1:str=aaaaa,n=5,k=3$ 此种情况显然是 $s_1=a,s_2=aa,s_3=aa$ 最好的。

$ep2:str=aaabbc,n=6,k=3$ 此种情况显然 $s_k=abbc$ 是最优的。

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;
    }
}