2019-2020 ICPC, NERC, Northern Eurasia Finals L题 Lexicography【字符串构造】

传送门：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
*/