Lexicography——CF1267L构造题

简介: 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;
}



目录
相关文章
CF219A k-String(数学分析)
CF219A k-String(数学分析)
70 0
|
算法 应用服务中间件 AHAS
CF1321C Remove Adjacent(周围串删除)(贪心算法)
CF1321C Remove Adjacent(周围串删除)(贪心算法)
57 0
|
机器学习/深度学习 人工智能 算法
CF1550A Find The Array(贪心算法)
CF1550A Find The Array(贪心算法)
38 0
|
缓存 NoSQL
KUC720AE101 ABB 遵循提取、解码和执行步骤
KUC720AE101 ABB 遵循提取、解码和执行步骤
147 0
KUC720AE101   ABB 遵循提取、解码和执行步骤
|
机器学习/深度学习
CF2A Winner(map+思维)
CF2A Winner(map+思维)
97 0
|
人工智能
CF1660C Get an Even String(贪心)
CF1660C Get an Even String(贪心)
103 0
|
Java 关系型数据库 MySQL
流程图详解 new String(“abc“) 创建了几个字符串对象
这道题是我之前的面试题文章《Java 基础高频面试题(2021年最新版)》里的第10题,今天通过字节码和流程图来跟大家详解一下完整的执行过程。 同时也会涉及一些字符串常量池的相关知识,这块内容网上现在的说法有太多错误了
298 0
流程图详解 new String(“abc“) 创建了几个字符串对象
|
Java
Java部分A+B正整数A的“DA(为1位整数)部分”定义为由A中所有DA组成的新整数PA。例如:给定A = 3862767,DA = 6,则A的“6部分”PA是66,因为A中有2个6。现给定A、DA
Java部分A+B正整数A的“DA(为1位整数)部分”定义为由A中所有DA组成的新整数PA。例如:给定A = 3862767,DA = 6,则A的“6部分”PA是66,因为A中有2个6。现给定A、DA
128 0
|
BI
CF1367 D. Task On The Board(构造)
CF1367 D. Task On The Board(构造)
86 0