# 直线上的服务站：连续分组与中位数

## 将选址转成分组

排序后记坐标为 $x_1\le\cdots\le x_N$ .按服务站从左到右的顺序，每个站服务一段连续房屋；距离并列时也可以按连续区间分配。对一个固定分组，绝对距离和在中位数处最小，因此存在所有服务站都位于房屋坐标的最优方案。

可以把最优方案写成恰好 $M$ 个非空连续组。若某个站没有房屋关联，因 $M\le N$ ，可以拆分一个含至少两个房屋的组并增加一个服务站，代价不会增加。重复坐标不影响此论证。

令 $P_i=\sum_{j=1}^ix_j$ ，$P_0=0$ .一个站服务 $[l,r]$ 的最小代价为

$$C(l,r)=x_q(q-l+1)-(P_q-P_{l-1})+(P_r-P_q)-x_q(r-q),\qquad q=\lfloor(l+r)/2\rfloor.$$

前缀和让一次代价计算只需常数时间。

## 动态规划与决策单调性

令 $D_t(r)$ 表示前 $r$ 个房屋分成 $t$ 组的最小代价。初值为 $D_0(0)=0$ ，其余不可行状态为正无穷。

$$D_t(r)=\min_{t-1\le j<r}\{D_{t-1}(j)+C(j+1,r)\},\qquad r\ge t.$$

直接枚举转移需要 $O(MN^2)$ 时间。区间代价具有 Monge 性质：对于 $a\le b\le c\le d$ ，有

$$C(a,c)+C(b,d)\le C(a,d)+C(b,c).$$

证明可以看右端点扩展的增量：

$$C(l,r+1)-C(l,r)=x_{r+1}-x_{\lfloor(l+r+1)/2\rfloor}.$$

固定 $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](std.cpp)。出题人解法按“最右服务站的位置”建状态，预处理相邻服务站之间的代价，见完整[端点选址解法](solution-alternative.zh.md)及 [alternative.cpp](alternative.cpp)。该方法也是分治动态规划，时间 $O(N^2+MN\log N)$ 、空间 $O(N^2)$ .连续组中位数方案省去了二次预处理表；两份程序都覆盖完整范围。实际耗时和内存见[测量记录](../../../docs/benchmark-R25.json)。

出题人贡献：端点选址状态、区间代价及分治优化。GPT-6：应用经典中位数分组与 Monge 优化，补齐两种状态的证明、双语说明和标准 C++17 程序。小规模用朴素区间动态规划核对，正式数据用独立 SMAWK 行最小值算法核对。