传送门:L. Lexicography

题意

给你一个字符串,你需要把它分成n个长度为m的字符串,要求按字典序由小到大排序后,第k个字符串的字典序尽可能小。答案可能有多种,只需输出任意一种。

思路

首先排序原字符串,假设为$s$。

先考虑前k个字符串。按列填字符,举个例子:

input

6 5 6
aabbbbccddefghzzzzzzzzzzzzzzzz

output

azzzz
azzzz
bczzz
bczzz
bdezz
bdfgh

就这个例子来说,n=6,m=5,k=6,第1列的1~k行按字符串$s$的正序填充,然后找第1列的第k行(字符是b)这一位置向上有多少个字符与它相同,显示是4个。那么也就意味着(k-4+1)\~k行这些字符串的字典序还不能确定,但是1\~(k-4)行的字典序一定要比后面的字符串都小,因为由第1列的字符就已经能比较出大小了,那么可以把1\~(k-4)行后面的列全部填充完,就用字符串$s$后面大的字符填充,从下到上,从右到左填充即可,这样就能保证这些字符串的字典序还是保持升序。第1列这么填完之后,剩下的列也是同样的填法。

对于k行之后的字符,只要把剩下的字符串$s$按正序填充就行了,保证它们字典序是升序的。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,k;
char s[N*N]; // 数组别开成N,是N*N!
char ans[N][N];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>k>>s+1;
    int len=strlen(s+1);
    sort(s+1,s+len+1);
    int p1=1,p2=len;
    int pos=1;
    for(int i=1;i<=m;i++) // 第i列
    {
        for(int j=pos;j<=k;j++) // 第j行
        {
            ans[j][i]=s[p1++];
        }
        char c=ans[k][i];
        int cnt=0; // 从第k行向上和ans[k][i]相同的个数
        for(int j=k;j>=pos;j--)
        {
            if(ans[j][i]==c)cnt++;
            else break;
        }
        int t=k-cnt+1; // 下一次开始遍历的行的位置
        for(int k2=m;k2>=i+1;k2--) // 列
        {
            for(int k1=t-1;k1>=pos;k1--) // 行
                ans[k1][k2]=s[p2--];
        }
        pos=t;
    }
    for(int i=k+1;i<=n;i++) // 第k行之后
        for(int j=1;j<=m;j++)
            ans[i][j]=s[p1++];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            j==m?printf("%c\n",ans[i][j]):printf("%c",ans[i][j]);
    return 0;
}
/*
6 5 6
aabbbbccddefghzzzzzzzzzzzzzzzz
6 5 4
aabbbbccddefghzzzzzzzzzzzzzzzz
4 4 3
abfhabgiacdkacdj
5 3 4
aabbcccddddeeee
3 4 3
aabbbcddffgh
*/