题目大意

在一条直线上有 $n$ 个目标，坐标为 $x_i$。玩家从 $x_0$ 出发，只能在坐标为 $x_0 + kd$（$k$ 为整数）的补给点投掷小球。击中坐标为 $x_i$ 的目标需要消耗 $(x - x_i)^2$ 的能量，移动距离 $d$ 需要消耗 $t$ 能量。有 $m$ 位选手，每位选手的 $t$ 值不同，需要为每位选手计算击中所有目标的最小总能量。

算法思路

关键观察

1. 问题分解：将目标分为左侧（$x_i < x_0$）和右侧（$x_i > x_0$）两组独立处理
2. 投掷点选择：对于每个目标，最优的投掷点要么是前一个补给点，要么是后一个补给点
3. 代价函数：总代价可以表示为关于移动次数的二次函数

算法框架

1. 预处理阶段

• 将目标按坐标排序
• 分别处理左侧和右侧的目标
• 计算每个目标从前一个或后一个补给点投掷的最小平方代价
• 记录每个新区间的起始位置

2. 数学建模

设移动 $p$ 次，总代价为：

$$\text{cost} = t \cdot p + \sum_{i=1}^m (p \cdot d - a_i)^2 $$

展开后得到二次函数：

$$\text{cost} = m \cdot d^2 \cdot p^2 + (t - 2d \cdot \sum a_i) \cdot p + \sum a_i^2 $$

3. 查询处理

• 对所有查询按 $t$ 值排序（离线处理）
• 对于每个查询，在可能的区间内寻找使二次函数最小的 $p$ 值
• 使用前缀和、后缀和加速计算

4. 结果合并

对于每个选手，考虑两种策略组合：

• 左侧使用策略 A，右侧使用策略 B
• 左侧使用策略 B，右侧使用策略 A 取两种组合的最小值作为最终答案

算法复杂度

• 时间复杂度：$O((n + m) \log n)$
  • 排序：$O(n \log n)$
  • 预处理：$O(n)$
  • 查询处理：$O(m \log n)$
• 空间复杂度：$O(n + m)$

算法优势

1. 数学优化：利用二次函数的性质快速求最值
2. 分治思想：左右分开处理，降低问题复杂度
3. 离线处理：批量处理查询，避免重复计算
4. 数值稳定性：使用大整数类型防止中间结果溢出

实现细节

• 使用 __int128 类型处理大数运算
• 通过前缀和、后缀和优化区间查询
• 对目标和查询排序以提高缓存效率
• 分别处理左右两侧，最后合并结果

总结

本题通过巧妙的数学建模，将复杂的移动和投掷问题转化为二次函数优化问题，结合分治策略和离线处理，实现了高效的最优解计算。算法在保证正确性的同时，能够处理大规模数据输入。

算法标签：数学优化 分治算法 二次规划 排序二分 前缀和优化 离线查询