自动搬运

查看原文

来自洛谷，原作者为

	kyEEcccccc 输不了的

搬运于2025-08-24 22:25:10，当前版本为作者最后更新于2023-09-28 23:14:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

先忽略掉无穷解的判断，假设我们只需要不停地操作尽可能多的步骤。考虑一个贪心策略：对于一类糖果，存在某个时刻 $t_i$，到这个时刻如果还没有额外买一个这种糖果就会不合法了；当然也存在一个时刻 $s_i$，在此之前如果买了一个糖果就会不合法。那么我们每次取所有可以取的糖果里 $t_i$ 最小的那个糖果，如果发现没有能取的，或者有必须取的取不了，那就寄了。

现在考虑无穷解的问题。一个大胆的猜测是如果说进行到下一个 $A = \sum\limits_{i=1}^n a_i$ 的倍数轮次以后依然合法那就一定合法了。考虑这是为啥。我们发现当轮数是 $A$ 的倍数时候所有 $nf_i$ 都是整数，那么所有糖果都只有一种合法数值。如果这一次合法，上一次进行到 $A$ 的倍数也合法，那么可以无限模仿这一回合的方法进行下去。那么我们只需要模拟最多 $A$ 轮。

实现考虑使用一些堆和 set。