题目分析

我们需要最小化所有固定雕像与所有可移动雕像之间的曼哈顿距离之和，最多进行 K 次移动。

---

核心思路

1. 问题分解

曼哈顿距离可以按维度分解：

dist(s, m) = Σ|s_i - m_i|  (对每个维度 i)

因此总距离 = 各维度距离之和，各维度独立。

---

2. 单维度分析

对于单个维度：

• 固定雕像坐标：a₁, a₂, ..., a_N
• 可移动雕像坐标：b₁, b₂, ..., b_Q

最优策略是将所有可移动雕像移动到固定雕像的中位数附近。

关键观察：

• 当 N 为奇数时，中位数唯一
• 当 N 为偶数时，中位数有两个，但最优解在两者之间的任意位置效果相同

---

3. 移动代价计算

代码中的核心思想：

3.1 初始距离

for (int i = 0; i < N; i++) {
    ans += 1LL * Q * std::abs(a[i] - a[N / 2]);
}

这是所有固定雕像到中位数的距离之和 × Q（因为每个可移动雕像都要与所有固定雕像计算距离）。

3.2 移动收益

cnt[i] 数组存储了将可移动雕像向中位数移动特定"步数"能减少的总距离：

• cnt[k] 表示将所有需要移动 k 步的雕像移动后减少的总距离
• 移动的优先级：距离中位数远的雕像优先移动（因为收益更大）

3.3 具体计算

对于每个维度：

1. 排序固定雕像坐标
2. 统计每个可移动雕像需要移动多少步才能到达中位数区间
3. 计算移动这些步数能减少的总距离

---

4. 多维度整合

由于曼哈顿距离的可分离性，我们可以：

1. 对每个维度独立计算初始距离和移动收益
2. 汇总所有维度的初始距离得到基础答案
3. 汇总所有维度的移动收益，按收益大小排序
4. 用最多 K 次移动来获得最大收益

---

5. 算法流程

1. 预处理：对每个维度，排序固定雕像坐标
2. 初始距离：计算所有固定雕像到中位数的距离之和 × Q
3. 移动收益：对于每个可移动雕像，计算移动到中位数附近能减少的距离
4. 贪心选择：用 K 次移动优先选择收益最大的移动
5. 结果计算：初始距离 - 通过移动减少的距离

---

复杂度分析

• 排序：O(T × (N log N + Q log N))
• 统计移动收益：O(T × (N + Q))
• 贪心选择：O(N)
• 总复杂度：O(T × (N + Q) log N)

对于 N, Q ≤ 1e5, T ≤ 10 完全可行。

---

样例验证

样例 1

输入：
3 2 7
8 1
2 0
0 3
2
10 2
2 6

输出：
29

解释：经过 7 次最优移动后，最小曼哈顿距离和为 29。

样例 2

输入：
6 4 200
...（坐标省略）
3
...（坐标省略）

输出：
708

---

关键优化

1. 维度独立性：利用曼哈顿距离的可分性，各维度独立处理
2. 中位数性质：最优位置在中位数附近
3. 移动收益排序：优先进行收益最大的移动
4. 高效统计：使用前缀和等技术快速计算移动收益

---

算法标签

• 中位数优化 (Median Optimization)
• 贪心算法 (Greedy Algorithm)
• 曼哈顿距离 (Manhattan Distance)
• 多维处理 (Multi-dimensional Processing)

---

总结

本题通过分析曼哈顿距离的性质，将其分解为各维度独立的问题，然后利用中位数的优化性质和贪心策略，在 O(T × (N + Q) log N) 时间内找到最优解。核心在于发现最优位置在中位数附近，并优先进行收益最大的移动。