自动搬运

查看原文

来自洛谷，原作者为

	Otomachi_Una_ We will never forget those days, thanks for everything.

搬运于2025-08-24 23:04:55，当前版本为作者最后更新于2025-01-04 15:39:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

神题。

考虑我们要不每个数都是 $\infty$，要么从 $0,1,2,3,\dots$ 每个数只出现一次。

考虑这种构造：$0,1,2,3,\dots,k,\infty,\dots,\infty,k+1,\infty,\dots,\infty$。

这种构造能解决 $c\leq \mathcal O(n^2)$ 的情况。

考虑更牛一点，我们把 $0$ 挪到大概 $t=\frac n3$ 的位置。然后你发现每次增量都是 $t$ 的倍数，那我们强制在 $a_n$ 填最大，再左边再填一个更大的就能得到余数了。

大概是这样子的：$\infty\dots\infty,k+1,\infty\dots,\infty,0,1,2,\dots,k-1,\infty,\dots,\infty,k$。

这样子构造就是 $\mathcal O(n^3)$。