题意概述

给定两个长度为 ( N ) 的数列 ( A ) 和 ( B )，以及一个整数 ( K )。
你可以：

1. 将 ( A ) 中所有元素加上同一个整数 ( X )（( X ) 可以是任意整数）；
2. 修改 ( A ) 中最多 ( K ) 个元素的值（可以改为任意整数）。

目标是最小化
[ S = \sum_{i=1}^N |A_i - B_i| ]

---

关键思路

1. 转化问题

令 ( C_i = B_i - A_i )，则题目变为：
先给所有 ( C_i ) 加上同一个数 ( X )（即 ( A_i \to A_i - X ) 等价于 ( C_i \to C_i - X )），然后可以修改 ( K ) 个 ( C_i ) 的值（修改后可以直接让 ( |C_i| = 0 )），最后求 [ S = \sum_{i=1}^N |C_i| ] 的最小值。

---

2. 先考虑 ( K = 0 ) 的情况

当 ( K = 0 ) 时，不能修改任何数，只能整体平移 ( C )。
目标是最小化 [ \sum_{i=1}^N |C_i - X| ] 这等价于：已知数列 ( C )，求一个数 ( X ) 使得 ( C ) 到 ( X ) 的绝对距离和最小。
经典结论：( X ) 应取 ( C ) 的中位数。

所以当 ( K = 0 ) 时，最优解是：

1. 计算 ( D_i = B_i - A_i )。
2. 取 ( D ) 的中位数 ( m )。
3. 答案 ( = \sum |D_i - m| )。

---

3. 考虑 ( K > 0 ) 的情况

我们可以修改 ( K ) 个元素，意味着可以让 ( K ) 个 ( |C_i - X| ) 变为 0（因为可以任意修改 ( A_i ) 来匹配 ( B_i )）。

问题变为：

• 选择 ( K ) 个下标 ( i )；
• 选择一个 ( X )；
• 最小化 ( \sum |C_i - X| )，其中求和是对未被选择的 ( N-K ) 个元素进行的。

换个角度：
对于固定的 ( X )，我们可以选择 ( K ) 个 ( i ) 使得 ( |C_i - X| ) 最大，将它们“消除”（代价变为 0），剩下的 ( N-K ) 个元素的绝对值求和即为该 ( X ) 下的最优值。

因此，对于固定的 ( X )，最小值为： [ F(X) = \sum_{i=1}^N |C_i - X| - \sum_{j=1}^K \text{最大的 } |C_{i_j} - X| ] 即总和减去最大的 ( K ) 个绝对差。

我们需要找到 ( X ) 使 ( F(X) ) 最小。

---

4. 函数 ( F(X) ) 的性质

( \sum |C_i - X| ) 是分段线性凸函数，斜率变化点在 ( C_i ) 处。
减去最大的 ( K ) 个 ( |C_i - X| ) 相当于对每个 ( X ) 去掉 ( K ) 个绝对值最大的项。

这会导致 ( F(X) ) 也是分段线性函数，但可能不再是凸的？我们需要更系统地分析。

---

5. 重述为选择问题

设我们最终保留的 ( N-K ) 个元素下标集合为 ( S )，则总代价为 [ \sum_{i \in S} |C_i - X| ] 且我们可以自由选 ( X )。

对固定集合 ( S )，最优 ( X ) 是 ( { C_i : i \in S } ) 的中位数。
因此问题等价于： 选择 ( N-K ) 个元素构成集合 ( S )，使得它们的中位数尽量“集中”，从而绝对值总和最小。

---

6. 排序与对称处理

将 ( C_i ) 排序，记排序后数组为 ( D[1 \dots N] )。

如果 ( X ) 固定，那么最大的 ( |C_i - X| ) 一定来自两端：离 ( X ) 最远的 ( K ) 个点。
所以最优策略是：选择某个长度为 ( N-K ) 的连续子数组（在排序后的 ( D ) 中），然后取该子数组的中位数作为 ( X )，计算该子数组到其中位数的绝对距离和。

为什么是连续子数组？
因为如果选择的集合不连续，我们可以调整使它连续而不增加代价（中位数性质）。

---

7. 算法步骤

1. 计算 ( D_i = B_i - A_i )。
2. 将 ( D ) 排序。
3. 枚举长度为 ( N-K ) 的连续子数组 ( D[l \dots r] )，其中 ( r = l + (N-K) - 1 )。
4. 对该子数组，最优 ( X ) 是其中位数 ( m )：
   • 如果子数组长度 ( L = N-K ) 是奇数，中位数是 ( D[(l+r)/2] )。
   • 如果长度是偶数，中位数可以是 ( D[(l+r)/2] ) 或 ( D[(l+r)/2+1] ) 之间的任意数，为简便可取左中位数。
5. 计算该子数组的绝对距离和： [ \text{cost}(l, r) = \sum_{i=l}^r |D[i] - m| ] 这可以用前缀和快速计算：
   设 ( m ) 在排序后下标 ( mid )，则 [ \text{cost} = (m \cdot (mid-l+1) - \sum_{i=l}^{mid} D[i]) + (\sum_{i=mid}^r D[i] - m \cdot (r-mid+1)) ] 用前缀和可以 ( O(1) ) 计算。
6. 取所有 ( \text{cost}(l, r) ) 的最小值。

---

8. 复杂度

排序 ( O(N \log N) )，枚举连续子数组 ( O(N) )，每次计算 ( O(1) )，总复杂度 ( O(N \log N) )，可以接受。

---

9. 边界情况

• ( K = N ) 时，可以修改所有数，答案为 0。
• ( K = 0 ) 时，即取整个数组的中位数。

---

总结

本题核心是将问题转化为在排序差值数组上选择连续子数组，并求该子数组到其中位数的绝对距离和的最小值。
利用绝对值函数的性质和前缀和优化，可以在 ( O(N \log N) ) 时间内求解。