题解：AT_arc226_d [ARC226D] Penta-Queue

· · 题解

好题！

首先，我们要做的是让五个队列都升序，否则一直 pop 就倒闭了。

那考虑维持升序能干啥，队列是比较少的，所以不难想到归并排序，想想怎么归并两个升序队列到一个。

假设要把队列 i 归并到队列 j，因为已经有 i,j 自己升序，所以不难。不断把两队较小的队首弹到 j 的队尾即可。这样 i 就空了。

设 sz_x 为队列 x 的大小。归并需要的操作次数是 sz_i+sz_j。

回到题目，每次往队列 1 随机扔一个元素，为了维持升序，最坏情况队列 1 时刻只能有一个元素，每次 push 都要归并到别的序列。

归并到哪个队列呢？因为 push 比较多，所以需要归并到 sz 较小的队列，不然操作次数就炸了。但是一直往某个队列或者往多个队列，如果不再干点啥，sz 不久一定膨胀得很大。

一个想法是，归并到队列 2，等 sz_2 到达一个阈值 B 时，再把队列 2 归并到队列 3。然后化为子问题，等队列 3 到达 B^2 再合并到队列 4，队列 4 到达 B^3 再合并到队列 5。我们要求队列 5 不超过 B^4，即 B^4\ge Q。

你发现这样每对相邻队列的归并总复杂度是一致的，每往后一层规模大 B 倍但频率少 B 倍。大约都要 \frac{B(B+1)}{2}\times \frac{Q}{B} 次操作。总共就是 2(B+1)Q，取 B=9 恰好满足 9^4>5000 且不超过限制，做完了。

代码太好写了不放。