题解：CF1896G Pepe Racing

Exscallop64_ · 2026-07-25 17:00:54 · 题解

第一步要想到。

Hint：怎么尽可能少地问出最大值？

对于 n^2 个 pepe，考虑分 n 组，第 i 组的编号集合为 S_i。设 m_i 表示第 i 组速度最大的 pepe。那么我们可以先用 n 次得到每组的 m_i，然后再问一次 \{m_1,m_2,\dots,m_n\} 即可得到最大值，代价 n+1 次。

既然要最大的 n^2-n+1 个，那么我们只要不断获取最大值即可。可以发现若最大值 x 在第 p 组，那么取走这个最大值后只会影响 m_p。

因此先把 x 从 S_p 中丢掉，然后更新扔掉之后 S_p 的最大值。注意可能 \vert S_p \vert < n，此时应当从别的组拿一些过来，注意这些拿走的 pepe 不应当是它那个组的最大值。

那么每次查出最大值需要 1 次 \{m_1,m_2,\dots,m_n\}，更新 S_p 又需要一次。扔掉原来的最大值并找到现在的最大值共计 n^2-n 次，因此总次数为 n+1+2(n^2-n)=2n^2-n+1，多了一个 n。

哪里浪费了？可以发现当剩下 2n-1 个 pepe 时（即还有 n 个没确定时），可以发现此时 n 个组的 m_i 就是我们候选的，其余的 n-1 个 pepe 不可能被选中。

那么考虑维护一个集合 T，初始时 T=\{m_1,m_2,\dots,m_n\}，每次查出 T 的最大值并扔掉，然后抓一个不可能选中的 pepe 丢进 T 中占位，最后一个候选的 pepe 用排除法。这样就只要 n-1 次询问了。

计算一下，此时的次数是 n+2(n^2-2n+1)+n-1=2n^2-2n+1 足以通过。