Lexicography——CF1267L构造题

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

样例输出1

af
bc
ed

样例输入2

2 3 1

样例输出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;
}