cf1348 C. Phoenix and Distribution(思维)

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

题意:

把一个长为 n 的字符串分成 k 个非空子串,顺序任意,不必连续。让字典序最大的子串 t 最小,输出 t

思路:

首先对字符串排序,把前 k 个字符分别放入每个子串中,让每个子串有一个字符

如果前 k 个字符不全相同,那么把后面的字符全给第 1 个子串,输出第 k 个子串(即a[k-1])

如果前 k 个字符全都相同,后面的字符不全相同,那就把后面的字符全给任意一个子串,输出该子串

否则,把后面的字符平均分配给每个串(浮点数向上取整)

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
char s[N];

signed main()
{
    int T; scanf("%d", &T); while(T--)
    {
        int n, k; cin >> n >> k >> s;
        sort(s, s+n);
        if(s[0] != s[k-1]) cout << s[k-1] << '\n';
        else if(s[k] != s[n-1]) cout << s+k-1 << '\n';
        else cout << s[0] << s+n-(int)ceil(1.0*n/k-1) << '\n';
    }

    return 0;
}

上一篇:Phoenix使用


下一篇:cf638 A. Phoenix and Balance(思维)