题解：AT_diverta2019_2_b Picking Up

akaryan · 2025-11-27 19:48:44 · 题解

题意

在二维平面上有 n 个球，第 i 个球位于 (x_i, y_i)。选择两个整数 p,q，按以下规则收集所有球：

• 第一个球收集代价为 1。
• 后续若当前球坐标与前一个球坐标差为 (p,q)，则代价为 0，否则为 1。

求最小总代价。

思路

我们观察数据，发现 n 很小，所以我们可以枚举所有点对的差分向量 (dx,dy)，然后计算每个可能的 (p,q) 能形成多少条链覆盖所有点，最后取最小值即可。