直线上的服务站：连续分组与中位数¶
将选址转成分组¶
排序后记坐标为 \(x_1\le\cdots\le x_N\) .按服务站从左到右的顺序，每个站服务一段连续房屋；距离并列时也可以按连续区间分配。对一个固定分组，绝对距离和在中位数处最小，因此存在所有服务站都位于房屋坐标的最优方案。
可以把最优方案写成恰好 \(M\) 个非空连续组。若某个站没有房屋关联，因 \(M\le N\) ，可以拆分一个含至少两个房屋的组并增加一个服务站，代价不会增加。重复坐标不影响此论证。
令 \(P_i=\sum_{j=1}^ix_j\) ，\(P_0=0\) .一个站服务 \([l,r]\) 的最小代价为
前缀和让一次代价计算只需常数时间。
动态规划与决策单调性¶
令 \(D_t(r)\) 表示前 \(r\) 个房屋分成 \(t\) 组的最小代价。初值为 \(D_0(0)=0\) ，其余不可行状态为正无穷。
直接枚举转移需要 \(O(MN^2)\) 时间。区间代价具有 Monge 性质：对于 \(a\le b\le c\le d\) ，有
证明可以看右端点扩展的增量：
固定 \(r\) 时，此增量随 \(l\) 增大而不增。把从 \(c\) 扩展到 \(d\) 的增量相加，就得到上述不等式。给每个候选列加上 \(D_{t-1}(j)\) 不会破坏它，因此每行取最小编号的最优分割点时，分割点随 \(r\) 不减。若两个最优点交叉，用不等式交换它们不会增加代价；在平局时选择较小编号便排除了严格逆序。
分治计算一层¶
已知目标区间 \([L,R]\) 的决策位于 \([A,B]\) .先取中点 \(r\) ，枚举 \([A,\min(B,r-1)]\) 找最优点 \(j\) ，再递归计算左半区间，决策上界设为 \(j\) ；右半区间的决策下界设为 \(j\) .每层从目标 \([t,N]\) 、决策 \([t-1,N-1]\) 开始，严格更小时才更新最优点以保持最小编号平局规则。
动态规划枚举了每一种最后一组，故状态值正确；Monge 单调性保证分治没有漏掉最优决策。答案为 \(D_M(N)\) .
实现、复杂度与比较¶
每层分治在同一递归深度总共扫描 \(O(N)\) 个候选，递归深度 \(O(\log N)\) .含排序，总时间 \(O(N\log N+MN\log N)\) ；滚动两层动态规划，额外空间 \(O(N)\) .距离和最多 \(N\cdot10^8\) ，使用 64 位整数，正无穷取 \(2^{60}\) .
首选 std.cpp。出题人解法按“最右服务站的位置”建状态，预处理相邻服务站之间的代价，见完整端点选址解法及 alternative.cpp。该方法也是分治动态规划，时间 \(O(N^2+MN\log N)\) 、空间 \(O(N^2)\) .连续组中位数方案省去了二次预处理表；两份程序都覆盖完整范围。实际耗时和内存见测量记录。
出题人贡献：端点选址状态、区间代价及分治优化。GPT-6：应用经典中位数分组与 Monge 优化，补齐两种状态的证明、双语说明和标准 C++17 程序。小规模用朴素区间动态规划核对，正式数据用独立 SMAWK 行最小值算法核对。