题解

思路

先将老鼠坐标和洞穴按位置排序。数轴绝对值距离满足不交叉交换不劣：若 $x_a\le x_b$ 而 $p_u\le p_v$，则

$$|x_a-p_u|+|x_b-p_v|\le |x_a-p_v|+|x_b-p_u|.$$

因此存在最优方案，使分给每个洞的老鼠在排序后都是连续的一段。

设处理完若干个洞后，$dp_i$ 表示安置前 $i$ 只老鼠的最小代价。处理位置为 $p$、容量为 $c$ 的新洞，令

$$S_i=\sum_{t=1}^{i}|x_t-p|.$$

若新洞接收第 $k+1$ 到第 $i$ 只老鼠，则

$$ndp_i=\min_{i-c\le k\le i}\{dp_k+S_i-S_k\} =S_i+\min_{i-c\le k\le i}(dp_k-S_k).$$

括号内是一个滑动窗口最小值，可用单调队列维护。

做法

子任务 1：枚举每只老鼠进入的洞

递归枚举每只老鼠选择的洞，检查容量并统计距离。复杂度为 $O(m^n n)$。

子任务 2：朴素分组动态规划

枚举当前洞接收的老鼠数量，直接计算转移。复杂度为 $O(mn^2)$。

子任务 3：单调队列优化动态规划

对每个洞计算 $S_i$，按照 $i$ 递增维护候选 $dp_k-S_k$ 的单调队列，并删除 $k<i-c$ 的元素。每个候选只进出队一次，单个洞为 $O(n)$。

正确性证明

引理 1

存在一个最优方案，其中老鼠和洞穴的匹配不交叉。

证明。 对任意交叉匹配，由数轴绝对值距离的不等式交换两只老鼠的目标洞，总距离不增且各洞接收数量不变。反复交换即可消除全部交叉。$\square$

引理 2

动态规划转移枚举了处理当前洞后的全部最优可能。

证明。 由引理 1，当前洞接收的必是排序后一个连续后缀 $k+1,\ldots,i$，其长度不超过容量。转移枚举所有合法 $k$，前 $k$ 只由旧状态最优安置，新的一段距离恰为 $S_i-S_k$。$\square$

引理 3

单调队列得到的值等于朴素转移的最小值。

证明。 处理 $i$ 时队列中恰保留窗口 $[i-c,i]$ 内的候选下标，并按 $dp_k-S_k$ 单调递增，故队首就是转移所需的最小候选。$\square$

定理

算法输出最小总移动距离；无可行方案时输出 $-1$。

证明。 由引理 2，动态规划完整覆盖所有不交叉最优方案；由引理 3，优化不改变转移值。最终 $dp_n$ 有限当且仅当所有老鼠都能被容纳，其值即全局最优答案。$\square$

复杂度

排序复杂度为 $O(n\log n+m\log m)$，动态规划复杂度为 $O(nm)$，空间复杂度为 $O(n+m)$。