P5926 [JSOI2009] 面试的考验 题解

MarSer020 · 2023-10-17 20:22:27 · 题解

注意到这题数据随机。

我们充分发扬人类智慧：

将序列排序后，将每个位置向后 10 个位置的差记录下来，进行排序。

根据数学直觉，如果在记录的前 500 小个数中都没有在当前区间内的解，那么这次询问的值域一定不会很大，暴力计算即可。

这样速度快得飞起，在 n=10^5 时都可以在 1.39s 内卡过。