abc448f Authentic Traveling Salesman Problem 题解

· · 题解

题意非常清楚，此处不多赘述，下文设 \operatorname{Mx}=2 \times 10^7

首先如果仅按照 x 或 y 坐标，显然都是可以被极端数据卡掉的。

考虑把两种方式结合到一起，即先按 x 坐标排序，再按 y 坐标排序。

考虑将按 x 坐标排序后的 n 个点按顺序分成 K 组，每组内再重新按 y 坐标排序，满足每组大小为 \left \lfloor \frac{n}{K} \right \rfloor 或 \left \lfloor \frac{n}{K} \right \rfloor + 1.

（为方便表述，下文假定每组大小为 \frac{n}{K}）。

然后对于每个编号为奇数的组从下往上走，编号为偶数的组从上往下走，最后把 1 号点提出来放在开头即可。

考虑上界。最坏情况下每一组都是如下情况：设该组中最小的 x=L，最大的 x=R，从该组最右下角开始走，即开始时 x=R,y=1，每走一步 x 坐标都为 L 或 R 且每次都要变，最后走到最左上角，即最后 x=L,y=\operatorname{Mx}.

此时该组内的时间为 \operatorname{ans}=\operatorname{Mx}+(R-L) \times \frac{n}{K}.

则 K 组的 \operatorname{ans} 总和 =K \times \operatorname{Mx}+\operatorname{Mx} \times \frac{n}{K} =(K+\frac{n}{K}) \times \operatorname{Mx}.

对于每一组，从前一组到该组的总时间至多为 \operatorname{Mx}.

从 1 号点走到第一组第一个点时间至多 2 \times \operatorname{Mx}.

则严格上界 \operatorname{Ans}=(K+\frac{n}{K}+3) \times \operatorname{Mx}，则 K=\sqrt n 时 \operatorname{Ans} 最小，笔者使用的 K=250，此时 \operatorname{Ans}=9.26 \times 10^9 \le 10^{10}，符合条件。

代码实现简单