Lexicography——CF1267L构造题-阿里云开发者社区

Lexicography——CF1267L构造题

2022-05-31 219

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Lucy likes letters. She studied the definition of the lexicographical order at school and plays with it.At first, she tried to construct the lexicographically smallest word out of given letters. It was so easy! Then she tried to build multiple words and minimize one of them. This was much harder!

                    L. Lexicography
                    time limit per test3 seconds
                    memory limit per test512 megabytes
                    inputstandard input
                    outputstandard output

Lucy likes letters. She studied the definition of the lexicographical order at school and plays with it.

At first, she tried to construct the lexicographically smallest word out of given letters. It was so easy! Then she tried to build multiple words and minimize one of them. This was much harder!

Formally, Lucy wants to make n words of length l each out of the given n⋅l letters, so that the k-th of them in the lexicographic order is lexicographically as small as possible.

Input

The first line contains three integers n, l, and k (1≤k≤n≤1000; 1≤l≤1000) — the total number of words, the length of each word, and the index of the word Lucy wants to minimize.

The next line contains a string of n⋅l lowercase letters of the English alphabet.

Output

Output n words of l letters each, one per line, using the letters from the input. Words must be sorted in the lexicographic order, and the k-th of them must be lexicographically as small as possible. If there are multiple answers with the smallest k-th word, output any of them.

样例输入1

3 2 2
abcdef

样例输出1

af
bc
ed

样例输入2

2 3 1
abcabc

样例输出2

aab
bcc

题目大意：

给出一个长度为 n * l 的字符串，然后构造出一个字符串使得第 k 个字符串的字典序尽可能的小

PS:本题为一道特判题，可以根据自己的思路进行操作，只要使得第 k 个字符串的字典序尽可能小就是了

思路：按照每一位进行处理，在处理每一位的时候，首先处理前 k 个，然后在处理从k + 1往后的部分

int n, len, k;
string s[1008];
char yt[maxn];
int cnt[30];///用来统计数量
int main()
{
  cin >> n >> len >> k;
  cin >> yt;
  for (int i = 0; i < n * len; i++) {
    cnt[yt[i] - 'a']++;///统计字母的数量
  }
  int l = 0, r = k - 1;///左右两侧
  /// 做出前k个
  for (int i = 0; i < len; i++) {///长度,枚举每一位
    /// 一开始的时候先处理前k个
    for (int j = l; j < k; j++) {/// 1 -- k-1
      /// 遍历26个字母
      for (int t = 0; t <= 25; t++) {///按位按照字典序从a->z放置
        if (cnt[t]) {///有就放上
          s[j] += (t + 'a');///加上这个字符
          cnt[t]--;///对应的数量减小1
          break;///每次加上一个，然后直接break就好
        }
      }
    }
    for (int j = l; j < k; j++) {
      if (s[j][i] != s[k - 1][i]) {
        while (s[j].size() < len) {///如果同一位不同并且size不到 l 给他放上大的
          for (int t = 25; t >= 0; t--) {
            if (cnt[t]) {
              s[j] += ('a' + t);
              cnt[t]--;
              break;
            }
          }
        }
        l = j + 1;///第j个放好了就直接下一次从j+1开始
      }///就顺便将j+1赋值给 i
    }
  }
  /// 做从k+1开始的串
  for (int i = k; i < n; i++) {
    while (s[i].size() < len) {
      for (int t = 25; t >= 0; t--) {
        if (cnt[t]) {
          s[i] += ('a' + t);
          cnt[t]--;
          break;
        }
      }
    }
  }
  ///cout << s[1] << endl;
  sort(s, s + n);
  for (int i = 0; i < n; i++) {
    cout << s[i] << endl;
  }
  return 0;
}