Codeforces Round #638 (Div. 2)

题目链接

https://codeforces.com/contest/1348/problem/C

tag

构造， 思维

solution

将一个字符串分割成(k)个字符串， 求出(k)个字符串中字典序最大的字符串字典序最小的情况,如果第(1)小字符和第(k)小字符不相同,那么将第(2 ~ k)大的字符置为字符串,第(k+1~n)小的字符置于第(1)小字符后，答案即是第(k)小字符,如果第(1)小和第(k)小字符相同,那么先将这(k)个字符平均分配，如果剩下的(n-k +1)个字符相同 即第(k+1)小字符和第(n)小字符相同,那么我们将这(n-k+1)个字符均匀分配到(k)个所求字符串上,否则，我们将这(n-k+1)个从小到大全接在前(k)小个中第(i)个字符后，对于任意一种本质不同的其他放置方案(即不全部将所有字符依次放入第(j)个字符后, (j eq i)),我们将某一个字符(c)放置到了前(k)小中第j个字符后( (j eq i))，我们可以设此时(c)在(j)的第(pos)位,在(i)中第(pos)位为第(pos - k + 1)小字符(ch), (ch < c),字典序更大,所以将将这(n-k+1)个从小到大全接在前k小个中某个字符后,又前(k)小字符相等，不妨直接接在第一个字符后，此时所有放置方案中字典序最大的字符串的字典序最小

code

//created by pyoxiao on 2020/07/09
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define CL(a, b) memset(a, b, sizeof(a))
using namespace std;
const int mod = 1e9 + 7;
LL fpow(LL a, LL b, LL p = mod){LL ans = 1; a %= p; while(b) {if(b & 1) ans = ans * a % p; b >>= 1; a = a * a % p;} return ans;}
LL gcd(LL a, LL b){return b == 0 ? a : gcd(b, a % b);}
const int N = 1e5 + 7;
int n, k;
char s[N];
void solve() {
    cin >> n >> k >> (s + 1);
    sort(s + 1, s + n + 1);
    if(s[1] != s[k]) {
        cout << s[k] << '
';
        return ;
    }
    cout << s[1];
    if(s[k + 1] == s[n]) {
        for(int i = 1; i <= (n - k) / k  + (!!((n - k) % k)); i ++) cout << s[k + 1];
        cout << '
';
        return;
    } 
    for(int i = k + 1; i <= n; i ++) cout << s[i];
    cout << '
';
}
int main() {
    int T = 1;
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> T;
    while(T --) 
        solve();
    return 0;
}