好题解
baoba
·
·
题解
首先，我们要考虑的是，当它的头部位于问题陈述中的条件时，我们如何确定它是否能抓住当它的头部位于 x=k_0。
考虑一个序列 (Y_1,Y_2,...,Y_N)，由从头部到每个宝藏的距离 ∣X_i-k_0∣(1≤i≤N) 组成，按升序排序。如果 Y_i≤L_i 对所有 1≤i≤N，那么它就可以在满足条件的情况下抓住它们，具体来说就是用第i条腿去抓取由Y_i的宝物。另一方面，如果 Y_i>L_i 则不存在符合要求的夺宝方法，因为至少 (N-i+1) 个宝藏距离头部至少有 (L_i+1) 但最多有 (N-i) 条腿可以抓住它们。
天真地认为，可以将 (Y_1,Y_2,...,Y_N)，使用快速排序等算法只需使用快速排序等算法，可以在 O(N \log N) 的时间内完成，或者甚至可以检查与 x=k_0 两边最近的宝藏，总共只需 O(N) 时间，因此决策问题总共只需 O(N \log N) 或 O(N) 时间。
然而，头部候选人的范围是 -2×10^{18}≤x≤2×10^{18} ，因此几乎不可能在规定时间内考虑所有这些候选项。取而代之的是，我们要考虑何时答案会从 x=k_0 变为 x=k_0+1.
- 如果 x=k_0 满足条件，但 x=k_0+1 不满足条件
在这种情况下，在 x=k_0 之间的有效对应关系应该变得无效。也就是说，应该有
1. 如果 $x=k_0$ 不满足条件，但 $x=k_0+1$ 满足条件
在这种情况下，在 $x=k_0$ 应该变为有效。也就是说，应该有 $1≤i,j≤N$ 这样 $k_0+1-L_j≤X_i≤k_0+1+L_j$ 和 $(X_i<k_0-L_j$ 或 $k_0+L_j<X_i)$. 这样 $k_0$ 应为整数，仅限于具有 $k_0=X_i-L_j-1$，因此最多有 $N^2$ 个这样的候选数。
因此，集合 $S={X_i+L_j∣1≤i,j≤N}⋃{X_i-L_j-1∣1≤i,j≤N}$ 最多有 $2N^2$ 个元素。当其元素按升序排序为 $S_1,S_2 ,...,S_{∣S∣}$ 则对于每 $2≤i≤∣S∣$, 所有 $x$ 与 $S_{i-1}+1≤x≤S_i$ 满足条件，当且仅当 $x=S_i$ 满足条件。这里，在 $x≤S_1$ 和 $S_{∣S∣}+1≤x$ 永远不会满足条件，因为当头部足够远时，不可能满足条件。
因此，只要确定 $x=S_i$ 是否满足每个 $2≤i≤∣S∣$.对 $S$ 的代价是 $O(N^2 \log N)$，检查每个元素的总成本为 $O(N^3)$ $($ 或 $O(N^3 \log N))$ 的时间，因此问题的解决速度已经足够快了。