题解

问题分析

这是一个贪心构造问题。我们需要重新排列数字，使得所有长度为 $K$ 的子串中最大的那个尽可能小。

关键观察

1. 最大子串的位置：长度为 $K$ 的最大子串通常出现在数字的末尾部分
2. 贪心策略：将较大的数字尽量放在前面，但避免在末尾形成大的子串
3. 构造技巧：通过特定的排列模式来平衡整体数字大小和局部子串大小

算法思路

分段构造 + 贪心合并：

第一阶段：处理末尾大数字

for (int i = 9; i; i--) {
    while (large.size() < K - 1 && D[i]) {
        D[i]--;
        large += '0' + i;
    }
}
std::reverse(large.begin(), large.end());

• 从大到小取数字，构建末尾的 $K-1$ 个字符
• 反转后这些大数字会被放在构造结果的末尾

第二阶段：剩余数字分组

for (int i = 1; i < 10; i++) {
    while (D[i]) {
        D[i]--;
        s.push_back(std::string(1, '0' + i));
    }
}

• 将剩余的所有数字单独作为字符串存入数组

第三阶段：贪心合并

while (l > st) {
    s[l++] += s[st++];
    if (l == s.size()) {
        while (l > st && s[l - 1] == s.back()) {
            l--;
        }
    }
}

• 将小的数字段合并到大的数字段后面
• 保持字典序平衡，避免产生过大的子串

算法步骤

1. 读入 $K$ 和数字频数 $D$
2. 预处理末尾：用最大的数字填充末尾 $K-1$ 个位置
3. 分组剩余数字：每个数字单独成组
4. 贪心合并：通过特定的合并策略平衡数字分布
5. 拼接结果：合并后的数字段 + 预处理的大数字段
6. 输出构造结果

复杂度分析

• 预处理：$O(S)$，其中 $S$ 是数字总数
• 合并过程：均摊 $O(S)$
• 总复杂度：$O(\sum S)$，满足数据范围要求

构造原理

这种构造方法的核心思想是：

• 分散大数字：避免大数字连续出现形成大的子串
• 平衡分布：通过合并让数字大小分布更加均匀
• 控制末尾：特别处理末尾部分，因为长度为 $K$ 的子串会覆盖到末尾

样例验证

样例1：$K=2$, 数字 $1,2,3,3$

• 构造过程：
  • 末尾处理：取一个3 → large = "3"
  • 剩余数字：["1","2","3"]
  • 合并后得到 "231" + "3" = "2313"
  • 子串：23, 31, 13，最大为31 ✓

样例2：$K=7$, 更多数字

• 通过类似的贪心策略得到最优排列
• 验证最大子串确实较小

算法标签

• 贪心算法
• 字符串构造
• 组合优化
• 字典序处理
• 分治合并