题目描述

难度分:$1800$

输入$n(1 \leq n \leq 1000)$，$m(1 \leq m \leq 1000)$，$k(1 \leq k \leq n)$和$n \times m$个小写字母。

用这$nm$个字母，构造$n$个长为$m$的字符串，这$n$个字符串需要按照字典序从小到大排列。

最小化第$k$个字符串的字典序，然后输出这$n$个字符串。

输入样例$1$

3 2 2
abcdef

输出样例$1$

af
bc
ed

输入样例$2$

2 3 1
abcabc

输出样例$2$

aab
bcc

算法

贪心构造

思路不难，但是写起来还挺繁琐的。先遍历$s$，预处理出一个字母频数表$cnt$，然后依次考虑第$1$个位置到第$m$个位置。假设构造出来的$n$个字符串存储在矩阵$mat_{n \times m}$中，分为以下两种情况：

1. 考虑所有字符串的首字母，对于第$k$个字符串的首字母，检验它最小可以是哪个字母。非常容易检验，按照字典序遍历字母频数表$cnt$，看前几个字母的频数之和能够不小于$k$，第$k$个字符串的首字母就应该是满足$\Sigma_{letter=a}^{c}cnt[letter] \geq k$的最小字母$c$，而前$k-1$个字符串的首字母按照字典序，用不大于$c$的字母填好即可。
2. 考虑非首字母，假设当前考虑第$j$个字母（$j \gt 1$），检查第$j-1$列是从哪一行$l$开始满足$mat[l][j-1]=mat[k][j-1]$的。此时说明矩阵$mat$的第$j$列从第$l$行到第$k$行都是字母$mat[k][j-1]$，此时就要求第$j$列满足第$l$行到第$k$行的字母是单调不减的，又按照第一种情况的策略填字母（因为第$j-1$列已经满足$mat[row][j-1] \lt c$，$row \lt l$，所以第$j$列不用考虑第$1$到$l-1$行也能保证前面的字符串字典序更小）。看当前剩下的字母中，前几个字母的频数之和能够不小于$k-l+1$，第$k$个字符串的第$j$个字母就应该是满足$\Sigma_{letter=a}^{c}cnt[letter] \geq k-l+1$的最小字母$c$，而第$l$行到第$k-1$行就按照字典序，用不大于$c$的字母填好即可。

遍历完$m$列之后，最小的第$k$个字符串就已经构造好了，其他位置的字符串长什么样已经不重要。此时矩阵$mat$中还有一些位置是没有填字母的，把剩余字母按照字典序排列好，然后按行充填矩阵中的所有空位即可。

复杂度分析

时间复杂度

这个算法本质上就是在充填大小为$n \times m$的字符矩阵$mat$，只是对于第$k$行的关键列位置需要遍历字母a~z表来确定每列所要填的最小字母。因此，算法的时间复杂度为$O(nm)$。

空间复杂度

构造出来的字符矩阵$mat$消耗的空间为$O(nm)$。$s$串对应的每个字母的频数表$cnt$消耗的空间为$O(\Sigma)$，其中$\Sigma$表示字符集大小，本题中为$26$。$s$串是输入，不算做额外空间，因此整个算法的额外空间复杂度应该为$O(nm+\Sigma)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 1001;
int n, m, k, cnt[30];
char s[N*N], mat[N][N];

int main() {
    scanf("%d%d%d", &n, &m, &k);
    scanf("%s", s + 1);
    memset(cnt, 0, sizeof(cnt));
    for(int i = 1; i <= n*m; i++) {
        cnt[s[i] - 'a']++;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            mat[i][j] = '.';
        }
    }
    for(int j = 1; j <= m; j++) {
        // 尝试让当前位置为字母c
        if(j == 1) {
            int sum = 0;
            char kc;
            for(char c = 'a'; c <= 'z'; c++) {
                sum += cnt[c - 'a'];
                if(sum >= k) {
                    kc = c;
                    break;
                }
            }
            int i = 1;
            for(char c = 'a'; c <= kc && i <= k; c++) {
                while(cnt[c - 'a'] > 0 && i <= k) {
                    mat[i][j] = c;
                    cnt[c - 'a']--;
                    i++;
                }
            }
        }else {
            int l = 0;
            char c = mat[k][j - 1];
            for(int i = 1; i <= k; i++) {
                if(mat[i][j - 1] == c) {
                    l = i;
                    break;
                }
            }
            int sum = 0;
            char kc;
            for(char c = 'a'; c <= 'z'; c++) {
                sum += cnt[c - 'a'];
                if(sum >= k - l + 1) {
                    kc = c;
                    break;
                }
            }
            int i = l;
            for(char c = 'a'; c <= kc && i <= k; c++) {
                while(cnt[c - 'a'] > 0 && i <= k) {
                    mat[i][j] = c;
                    cnt[c - 'a']--;
                    i++;
                }
            }
        }
    }
    vector<char> remain;
    for(int i = 0; i < 26; i++) {
        while(cnt[i] > 0) {
            remain.push_back('a' + i);
            cnt[i]--;
        }
    }
    int index = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(mat[i][j] == '.') {
                mat[i][j] = remain[index++];
            }
            printf("%c", mat[i][j]);
        }
        puts("");
    }
    return 0;
}