题目理解

我们需要在 $R \times C$ 的棋盘上找到一个格子，使得 $N$ 个棋子移动到该格子的总曼哈顿距离最小。我们可以询问最多 $K$ 次某个格子的分数（总移动距离），最终输出全局最小分数。

关键观察：
设第 $i$ 个棋子在 $(X_i, Y_i)$，则格子 $(p, q)$ 的分数为：

该函数可分解为两个独立的一维函数：

其中 $g(p) = \sum |p - X_i|$，$h(q) = \sum |q - Y_i|$。因此，全局最小值等于 $g(p)$ 的最小值加上 $h(q)$ 的最小值。

算法设计

由于 $g(p)$ 和 $h(q)$ 都是凸函数（分段线性），我们可以分别用一维搜索找到最小值点。因为询问次数有限，我们采用黄金分割搜索（单峰函数的最优搜索方法），每次只需一个新的询问。

搜索步骤

1. 固定列，搜索最小行
   选择任意列（如 $q_0 = 1$），定义函数 $eval_1(p) = f(p, q_0)$。由于 $h(q_0)$ 为常数，$eval_1(p)$ 的最小值点就是 $g(p)$ 的最小值点。在区间 $[1, R]$ 上执行黄金分割搜索，得到最小行 $p^*$。

2. 固定行，搜索最小列
   固定行 $p^*$，定义函数 $eval_2(q) = f(p^*, q)$。在区间 $[1, C]$ 上执行黄金分割搜索，得到最小列 $q^*$，并得到全局最小分数 $f(p^*, q^*)$。

黄金分割搜索实现

• 每次将区间 $[l, r]$ 按黄金比例 $0.382$ 和 $0.618$ 选取两个内点 $a, b$。
• 比较 $eval(a)$ 与 $eval(b)$，若 $eval(a) < eval(b)$，则最小值在 $[l, b]$，否则在 $[a, r]$。
• 重复直到区间长度小于 $4$，然后遍历剩余点取最小值。
• 每次迭代只需询问一个新的点，另一个点可复用。

询问次数分析

黄金分割搜索每次迭代将区间长度缩小为原来的 $0.618$。对于最大范围 $10^7$，迭代次数约为：

两次搜索总询问次数约为 $68$ 次，小于 $K = 75$（最严格的情况），完全满足所有数据范围。

算法正确性

• 由于 $f(p, q) = g(p) + h(q)$，分别最小化 $g(p)$ 和 $h(q)$ 即可得到全局最小值。
• 黄金分割搜索适用于单峰凸函数，能准确找到最小值点。
• 当区间足够小时，遍历检查确保不会错过最小值。

代码实现要点

1. 询问缓存：用 map 存储已询问格子的分数，避免重复询问。
2. 离散调整：计算内点时取整，并处理可能的内点重合情况。
3. 边界处理：当 $R=1$ 或 $C=1$ 时，对应的一维搜索自动退化。

复杂度分析

• 时间复杂度：每次询问 $O(1)$，总询问次数 $O(\log R + \log C)$，可忽略不计。
• 空间复杂度：$O(K)$，用于缓存询问结果。

算法标签

• 树上倍增
• 最短路
• 贪心
• 搜索

总结

本题通过分离变量将二维问题转化为两个一维凸函数最小化问题，利用黄金分割搜索在有限询问内找到最优解。算法高效、可靠，适用于所有数据范围。