P6917 [ICPC2016 WF] Balanced Diet

kyEEcccccc · 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。