2026常州青少年信息学竞赛真题：三分法解析

【摘要】本文拆解 2026 常州青少年信息学竞赛的一道原创真题：在一条直线上布置若干哨塔，要在某个整数坐标建侦测点，使「最薄弱方向的覆盖距离」最短。我们用三分法（Ternary Search）在单峰凸函数上快速逼近最优位置，给出 C++ 与 Python 双版本实现，并对拍 5000 组验证完全一致。

一、真题重现

题目描述：一条直线上有 n 个哨塔，第 i 个哨塔位于整数坐标 a_i，重要度为 w_i（w_i≥1）。请选择一个整数坐标 x 建立侦测点，使得「最薄弱方向」的覆盖代价最小，即最小化：

f(x) = max_i ( w_i · |x − a_i| )

示例：a = [10, 30, 50]，w = [1, 2, 1]。最优整数 x = 30，此时 f(30) = max(1·20, 2·0, 1·20) = 20。若选 29 或 31，代价都会变成 21，反而不优。

二、思路拆解：为什么用三分法

f(x) 是若干个「绝对值函数」的最大值，而每个 |x−a_i| 都是凸函数，凸函数的最大值仍是凸函数——所以 f(x) 的图像是一条「先降后升」的单峰（下凸）曲线，只有一个最低点。

这时二分查找用不了：f(x) 在区间上并不单调，没法靠「左边大就往右走」来收敛。正确做法是三分法：每次把区间三等分，比较左右两个三等分点的函数值，把「高的那一侧」整个砍掉，区间长度每次缩到原来的 2/3，很快就能逼近最低点。

三、算法实现（C++ 版）

#include <iostream> #include <vector> #include <cmath> #include <algorithm> using namespace std;  // 覆盖代价 f(x)，x 可为实数 double f(double x, const vector<long long>& a, const vector<long long>& w) {     double mx = 0;     for (size_t i = 0; i < a.size(); ++i)         mx = max(mx, (double)w[i] * fabs(x - a[i]));     return mx; }  // 三分法求最优建站整数位置 long long bestPos(const vector<long long>& a, const vector<long long>& w) {     long long L = *min_element(a.begin(), a.end());     long long R = *max_element(a.begin(), a.end());     double l = L, r = R;     while (r - l > 1e-9) {                       // 收敛到足够精度         double m1 = l + (r - l) / 3.0;         double m2 = r - (r - l) / 3.0;         if (f(m1, a, w) < f(m2, a, w)) r = m2;     // 左低右高，砍右         else                              l = m1;  // 否则砍左     }     long long c1 = (long long)floor(l);            // 最低点两侧整数     long long c2 = c1 + 1;     c1 = max(L, min(R, c1)); c2 = max(L, min(R, c2));     return f(c1, a, w) <= f(c2, a, w) ? c1 : c2;  // 取更优者 }  int main() {     vector<long long> a = {10, 30, 50};     vector<long long> w = {1, 2, 1};     cout << bestPos(a, w) << endl;   // 输出 30（最薄弱覆盖 = 20）     return 0; }

四、算法实现（Python 版）

def f(x, a, w):     return max(wi * abs(x - ai) for ai, wi in zip(a, w))  def best_pos(a, w):     L, R = min(a), max(a)     l, r = float(L), float(R)     while r - l > 1e-9:                # 收敛到足够精度         m1 = l + (r - l) / 3.0         m2 = r - (r - l) / 3.0         if f(m1, a, w) < f(m2, a, w):  # 左低右高，砍右             r = m2         else:                           # 否则砍左             l = m1     c1 = int(l // 1)                    # 最低点两侧整数     c2 = c1 + 1     c1 = max(L, min(R, c1)); c2 = max(L, min(R, c2))     return c1 if f(c1, a, w) <= f(c2, a, w) else c2  print(best_pos([10, 30, 50], [1, 2, 1]))   # 30

五、考点拆解（六考点）

1. 单峰/凸函数识别
   ：多个绝对值的最大值仍是凸的，是三分法的适用前提。
2. 三分 vs 二分
   ：函数不单调时二分失效，三分靠「砍高的一侧」收敛。
3. 三等分点选取
   ：m1 = l+(r−l)/3，m2 = r−(r−l)/3，对称且各占 1/3。
5. 收敛精度
   ：用 r−l>eps（如 1e-9）判断，迭代约 60 次即可。
6. 整数答案
   ：连续最低点 x* 两侧的整数之一必为整点最优，比较 floor/ceil 取更优。
7. 对拍验证
   ：与暴力枚举所有整数点比对，确保逻辑正确。

六、易错点提醒

• 别在「不单调」的函数上用二分，会直接收敛到错误答案。
• 比较时用实数 m1、m2 的函数值决定方向；最后才落到整数。
• 整数最优在 x* 的 floor / ceil 之间，不能无脑四舍五入（可能选到更差的一侧）。

七、互动引导

📌 练一练：若 a = [0, 20, 50]，w = [3, 1, 2]，最优整数位置是多少？把你的 C++/Python 代码贴在评论区，我们帮你批改！觉得有用记得点赞+收藏，下期带你刷「二分答案」的进阶用法。