直线上的服务站：以最右服务站为状态¶

这是出题人的端点选址动态规划，由 alternative.cpp 实现，支持全部数据。先将房屋坐标排序为 \(x_1\le\cdots\le x_N\) .每个连续服务组可在其中位数建站，因此只考虑在房屋处建站不会失去最优解。

两站之间的代价¶

当相邻的两个站位于 \(x_i,x_j\) 时，中间房屋的贡献是

\[ W(i,j)=\sum_{i<k<j}\min(x_k-x_i,x_j-x_k). \]

对固定 \(i\) ，递增枚举 \(j\) ，维护最后一个更接近左站或与两站等距的下标 \(s\) ，初始 \(s=i\) .当 \(s+1<j\) 且 \(x_{s+1}-x_i\le x_j-x_{s+1}\) 时增加 \(s\) .用坐标前缀和 \(P\) 得到

\[ W(i,j)=P_s-P_i-x_i(s-i)+x_j(j-s-1)-(P_{j-1}-P_s). \]

分界只向右移动，全部 \(W\) 可在 \(O(N^2)\) 时间和空间内求出。

令 \(F_t(j)\) 为设置 \(t\) 个站、最右站位于房屋 \(j\) 时，所有编号不大于 \(j\) 的房屋的最小距离和。站的房屋下标严格递增，坐标允许相同。

\[ F_1(j)=x_j(j-1)-P_{j-1},\qquad F_t(j)=\min_{t-1\le i<j}\{F_{t-1}(i)+W(i,j)\}. \]

相邻站之间的房屋只会选择这两个站之一，最左站左侧和最右站右侧分别全部选择该端站。因此，转移精确拼接了已处理的左侧和新增站间区间；最终答案是

\[ \min_{M\le j\le N}\{F_M(j)+P_N-P_j-x_j(N-j)\}. \]

对 \(i\le j\le k\le l\) ，有 \(W(i,k)+W(j,l)\le W(i,l)+W(j,k)\) .可逐个房屋比较：位于中间 \([j,k]\) 的房屋，对应距离 \(A\ge B\) 、\(C\le D\) ，满足

\[ \min(A,C)+\min(B,D)\le\min(A,D)+\min(B,C). \]

位于外侧 \([i,j]\) 或 \([k,l]\) 的房屋则直接使用“把可选的端站移远不会降低距离”的单调性。端点贡献为零，重复坐标同样成立。把所有房屋的贡献相加得到不等式。

于是固定 \(t\) 时，最小编号的最优前驱随 \(j\) 不减。计算目标区间中点的最优前驱后，可用它限制左右两半的搜索区间，每层动态规划耗时 \(O(N\log N)\) .程序只依赖同一层的这个单调性。两层滚动数组保存 \(F\) ，用 64 位距离和及足够大的正无穷。

总时间 \(O(N^2+MN\log N)\) ，空间 \(O(N^2)\) .该状态直接分解相邻设施间的服务代价；中位数分组法用常数时间区间公式节省二次空间，作为首选。两个算法均通过全部正式数据。方法归出题人，GPT-6 补齐证明与安全实现；实测见性能记录。