自动搬运

查看原文

来自洛谷，原作者为

	Rainbow_qwq **

搬运于2025-08-24 23:02:03，当前版本为作者最后更新于2024-08-17 10:13:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

两个串之间 $1$ 匹配的次数总和为 $k\times l$，并且共有 $n$ 次匹配。

于是答案的下界为 $k\times l$ 个球放进 $n$ 个盒子，最小化最大的盒子中的 $1$ 个数，也就是 $\lceil \dfrac{k\times l}{n} \rceil$。

设 $ans = \lceil \dfrac{k\times l}{n} \rceil$，我们可以构造来达到这个上界：

• 对于第一个串，将前 $k$ 个位置变成 $1$。
• 对于第二个串，设这个串的前缀和数组为 $sum_i$。设 $sum_i = \min(\lfloor\dfrac{(i+1)\times ans}{k} \rfloor,l)$，然后差分即可。