「YLLOI-R1-T3」一路向北

Pollard_Rho · 2025-05-04 16:20:20 · 题解

Be like codeforces...

在我们将一个数字放入到对应队列之后，这个数字会出现在队列末尾。

注意到如果这个拥有队列编号的数字的数量小于 m 则无法把这个队列填充完。

所以，我们一开始把 0 藏在这个队列末，就取不出来。

接下来我们讨论除去这种情况，即所有数字的数量都大于等于 m，也即所有数字的数量都等于 m。

因为一个序列至多被操作 m 次，所以总共最多被操作 n\times m 次。每次操作，手上拿着的数字 p>0，则一定会操作一个序列，则在 n\times m 次后，我们就操作不了了，这时候的情况是所有的数字都归位了。也就是说，最后不但一定会取出 0，而且是在至多 n\times m 次操作后取出。