题目描述

给定一个长度为 $N$ 的整数数组 $A$，你需要创建另一个长度为 $N$ 的整数数组 $B$，数组 $B$ 被分为 $K$ 个连续的部分，并且如果 $i$ 和 $j$ 在同一个部分，则 $B[i] = B[j]$。

如果要求数组 $B$ 能够满足 $\sum |A[i] - B[i]|$ 最小，那么最小值是多少，请你输出这个最小值。

输入格式

输入包含不超过 25 组测试数据。

对于每组测试数据，第一行包含两个整数 $N$ 和 $K$。

接下来 $N$ 行每行包含一个整数，表示完整的数组 $A$。

当输入为一行 0 0 时，表示输入终止。

输出格式

对于每组数据，输出一个最小值。

每个结果占一行。

样例

7 2
6
5
4
3
2
1
7
0 0

9

样例解释

输入

$N = 7, K = 2$
$A = [6, 5, 4, 3, 2, 1, 7]$

要求

将 $B$ 分成 $K=2$ 个连续部分，每个部分内 $B$ 值相同。求 $\sum |A[i] - B[i]|$ 的最小值。

分析

我们需要将数组 $A$ 分成 2 段，每段内 $B$ 值相同。设第一段为 $A[1..m]$，第二段为 $A[m+1..7]$。

对于每一段，最优的 $B$ 值取为该段 $A$ 的中位数时，$\sum |A[i] - B[i]|$ 最小（这是绝对值偏差最小的性质）。

所以我们需要枚举分割点 $m$，计算每段中位数引起的绝对偏差和。

计算

首先排序？不对，因为 $B$ 是分段的，每段内 $B$ 相同，但 $A$ 顺序固定，不能排序。

实际上，对于一段连续区间 $[l, r]$，设该段内 $B$ 值为 $x$，则 $\sum_{i=l}^r |A[i] - x|$ 的最小值在 $x$ 取该区间 $A$ 的中位数时达到。

因此，我们可以预处理所有区间 $[l, r]$ 的最优值 $cost[l][r]$，即该区间取中位数时的绝对偏差和。

预处理

对于每个区间 $[l, r]$，我们需要找到中位数并计算偏差和。

由于 $N \le 2000$，可以 $O(N^2)$ 预处理。

方法：

1. 对每个左端点 $l$，维护一个有序列表（如平衡树或两个堆），依次加入右端点 $r$，动态维护中位数和偏差和。
   但计算偏差和需要知道所有元素与中位数的差绝对值之和，可以动态维护。

更简单的方法：

• 对每个 $l$，将 $A[l..r]$ 复制到临时数组，排序，找到中位数，然后计算绝对偏差和。复杂度 $O(N^2 \log N)$，对于 $N=2000$ 可能过大（$4\times10^6 \log 2000 \approx 4\times10^6 \times 11 \approx 4.4\times10^7$，可接受）。

动态规划

设 $dp[i][k]$ 表示将前 $i$ 个元素分成 $k$ 段的最小总偏差。

转移：

$$dp[i][k] = \min_{j < i} \{ dp[j][k-1] + cost[j+1][i] \}$$

其中 $cost[j+1][i]$ 是区间 $[j+1, i]$ 的偏差最小值。

初始化：$dp[0][0] = 0$，其他为无穷大。

答案：$dp[N][K]$。

样例计算

$A = [6,5,4,3,2,1,7]$

预处理 $cost[l][r]$： 例如：

• $[1,7]$：中位数是排序后的第 4 个数（从小到大：1,2,3,4,5,6,7），中位数 4，偏差和 = |6-4|+|5-4|+|4-4|+|3-4|+|2-4|+|1-4|+|7-4| = 2+1+0+1+2+3+3 = 12。
• 分成两段：枚举分割点 $m$（1~6）：
  • $m=1$：第一段 [1,1] 中位数 6，偏差 0；第二段 [2,7] 中位数 (1,2,3,4,5,7) 中位数 (3+4)/2=3.5，取 3 或 4？对于偶数个数，中位数可以是中间两个数的任意值，但绝对值偏差最小通常取中间两个数之间的任意值，但为了整数 $B$，可以取 3 或 4。偏差和：|5-3|+|4-3|+|3-3|+|2-3|+|1-3|+|7-3| = 2+1+0+1+2+4=10。总偏差 10。
  • $m=2$：[1,2] 中位数 (5,6) 取 5 或 6，偏差 |6-5|+|5-5|=1+0=1；[3,7] 中位数 (1,2,3,4,7) 取 3，偏差 |4-3|+|3-3|+|2-3|+|1-3|+|7-3| = 1+0+1+2+4=8；总 9。
  • $m=3$：[1,3] 中位数 5（排序 4,5,6），偏差 |6-5|+|5-5|+|4-5|=1+0+1=2；[4,7] 中位数 (1,2,3,7) 取 2 或 3，取 2 偏差 |3-2|+|2-2|+|1-2|+|7-2| = 1+0+1+5=7；总 9。
  • $m=4$：[1,4] 中位数 4.5 取 4 或 5，取 4 偏差 |6-4|+|5-4|+|4-4|+|3-4| = 2+1+0+1=4；[5,7] 中位数 (1,2,7) 中位数 2，偏差 |2-2|+|1-2|+|7-2| = 0+1+5=6；总 10。
  • $m=5$：[1,5] 中位数 4（排序 2,3,4,5,6），偏差 2+1+0+1+2=6；[6,7] 中位数 (1,7) 取 1 或 7，取 1 偏差 |1-1|+|7-1|=0+6=6；总 12。
  • $m=6$：[1,6] 中位数 3.5 取 3 或 4，取 3 偏差 3+2+1+0+1+2=9；[7,7] 偏差 0；总 9。

最小值为 9，所以输出 9。

数据范围

• $1 \le N \le 2000$
• $1 \le K \le 25, K \le N$
• 数组 $A$ 中元素的绝对值不超过 10000
• 测试数据不超过 25 组

算法分析

问题转化

将数组 $A$ 分成 $K$ 个连续段，每段内 $B$ 值相同，使得 $\sum |A[i] - B[i]|$ 最小。

对于每一段，最优的 $B$ 值是该段 $A$ 的中位数（如果长度为偶数，中位数可以是中间两个数的任意值，但绝对值偏差和是相同的，取任意中间值即可）。

因此，问题转化为：将数组 $A$ 分成 $K$ 段，每段的代价为该段元素与其中位数的绝对偏差和，求最小总代价。

预处理代价

设 $cost[l][r]$ 表示区间 $[l, r]$ 的代价，即该区间元素与其中位数的绝对偏差和。

如何高效计算 $cost[l][r]$？

• 暴力方法：对每个区间排序找中位数，复杂度 $O(N^2 \log N)$，对于 $N=2000$ 大约 $4\times10^6 \times 11 = 4.4\times10^7$，可接受。
• 优化：可以固定左端点 $l$，从小到大枚举右端点 $r$，用两个堆（最大堆和最小堆）动态维护中位数，并计算绝对偏差和。但计算绝对偏差和需要知道所有元素与中位数的差，可以维护两个堆的和。更简单的方法是直接维护有序列表（如平衡树），但实现较复杂。

由于 $N \le 2000$，$O(N^2 \log N)$ 在 25 组数据下可能稍慢但应该能通过（$25 \times 4.4\times10^7 \approx 1.1\times10^9$，可能超时）。需要优化。

优化预处理

注意到 $A[i]$ 的范围较小（绝对值 $\le 10000$），我们可以使用计数排序的思想。

对于每个左端点 $l$，维护一个频数数组 $cnt[20001]$（偏移 10000），以及当前区间的元素个数 $len$。随着 $r$ 增加，更新 $cnt[A[r]+10000]++$，然后可以 $O(10000)$ 找到中位数（因为值域只有 20001），并计算绝对偏差和。但计算绝对偏差和需要遍历整个值域，复杂度 $O(N^2 \times 10000)$ 太大。

更好的方法：
已知对于有序数组，绝对偏差和可以快速计算。设区间 $[l, r]$ 排序后为 $sorted$，中位数索引 $m = (l+r)/2$（下取整），则偏差和 = $\sum_{i=l}^r |sorted[i] - sorted[m]|$。
可以预处理前缀和 $pref$，则偏差和 = $sorted[m] \times (m-l+1) - (pref[m] - pref[l-1]) + (pref[r] - pref[m]) - sorted[m] \times (r-m)$。

因此，如果我们能快速得到区间排序后的数组，就可以 $O(1)$ 计算偏差和。但排序需要 $O(N \log N)$。

动态规划优化

DP 转移：$dp[i][k] = \min_{j < i} \{ dp[j][k-1] + cost[j+1][i] \}$。

如果直接枚举 $j$，复杂度 $O(K N^2)$，对于 $N=2000, K=25$，大约 $25 \times 4\times10^6 = 1\times10^8$，加上预处理 $O(N^2 \log N)$，可能勉强通过。

四边形不等式优化

由于 $cost[l][r]$ 满足四边形不等式，$dp$ 转移可以使用决策单调性优化，将复杂度降为 $O(K N \log N)$ 或 $O(K N)$。

但实现较复杂。

另一种思路：直接 DP 枚举段值

由于 $B$ 每段值相同，我们可以直接枚举每段的值，但值域太大（-10000 到 10000），不可行。

可行解法

考虑到 $N \le 2000$，$K \le 25$，直接 $O(K N^2)$ DP 加上 $O(N^2 \log N)$ 预处理在 25 组数据下可能可以接受（约 $25 \times (4\times10^6 + 1\times10^8) \approx 2.6\times10^9$ 运算，可能超时，但实际常数小可能通过）。

优化预处理

我们可以用 $O(N^2)$ 预处理 $cost[l][r]$，方法如下：

对于每个左端点 $l$，维护一个有序数组（初始为空），依次加入 $A[l], A[l+1], \dots, A[r]$，并维护中位数和绝对偏差和。

加入一个新元素 $x$ 时，我们需要将其插入有序数组，并更新中位数和偏差和。

• 插入位置可以用二分查找，$O(\log N)$。
• 偏差和更新：设原中位数为 $mid$，新中位数为 $mid'$。
  绝对偏差和的变化 = 新元素与中位数的偏差 + 旧元素偏差的变化。
  具体公式较复杂，但可以维护前缀和快速计算。

一个更简单的方法：直接使用两个堆（最大堆存较小一半，最小堆存较大一半）维护中位数，并维护两个堆的元素和，可以 $O(\log N)$ 更新中位数和偏差和。但计算绝对偏差和需要知道所有元素与中位数的差，我们可以维护：

• $sumLeft$：小于中位数的元素和
• $sumRight$：大于中位数的元素和
• $countLeft$, $countRight$

则绝对偏差和 = $mid \times countLeft - sumLeft + sumRight - mid \times countRight$。

当插入新元素时，根据与当前中位数的大小关系，插入到对应堆中，然后调整堆大小使中位数正确，并更新 $sumLeft$, $sumRight$ 等。

这样，对于每个左端点 $l$，遍历右端点 $r$，可以在 $O(N \log N)$ 时间内计算所有 $cost[l][r]$，总复杂度 $O(N^2 \log N)$。

最终算法

1. 预处理 $cost[l][r]$（$1 \le l \le r \le N$）。
2. 动态规划：$dp[i][k] = \min_{j < i} \{ dp[j][k-1] + cost[j+1][i] \}$。
3. 输出 $dp[N][K]$。

实现提示

• 注意数组下标从 1 开始。
• 使用 long long 存储代价，因为偏差和可能较大。
• 多组数据，每次重置数组。
• 当 $K \ge N$ 时，显然每段一个元素，代价为 0，但题目保证 $K \le N$。