2356. 连续子区间等值化的最小代价
1000ms
256MB
简单
前缀和与差分
题目描述
给定一个长度为 $N$ 的正整数序列 $A$，序列中的所有元素互不相同。每次操作可以将序列中的任意一个元素加 1 或减 1，每次操作的代价为 1。
求最少需要多少次操作，使得序列中存在连续的 $K$ 个元素，它们的值全部相等。
输入格式
- 第一行包含两个正整数 $N$ 和 $K$ ($1 \le K \le N \le 1000$)。
- 第二行包含 $N$ 个互不相同的正整数 $a_i$ ($1 \le a_i \le 1000$)，代表序列的初始元素。
输出格式
- 输出一个整数，表示最少的操作次数。
样例 1
输入 (Input)
3 2 3 6 1
输出 (Output)
3
样例说明
序列为 `3 6 1`，要求 $K = 2$ 个相邻元素相等。
- 选择前 2 个相邻元素 `3` 和 `6`：若将它们都变为 5，代价为 $|3 - 5| + |6 - 5| = 3$（也可以变为 3、4 或 6，最小代价均为 3）。
- 选择后 2 个相邻元素 `6` 和 `1`：若将它们都变为 1（或 6），最小代价为 $|6 - 1| = 5$。
- 综上，最少操作次数为 3。
- 对于 $100\%$ 的数据：$1 \le K \le N \le 1000$，且 $1 \le a_i \le 1000$，序列中元素互不相同。
- **算法提示**：
这是一个经典的**中位数**问题。
对于任意一个大小为 $K$ 的窗口 $\{x_1, x_2, \dots, x_K\}$，要使它们全部变为同一个数 $y$ 且操作代价最小，这个数 $y$ 必须是该窗口内所有元素排序后的**中位数**。
1. 利用滑动窗口，枚举所有可能的长度为 $K$ 的连续子区间。
2. 对于每个子区间，将其复制并排序，找出中位数（即排序后下标为 $K/2$ 的元素）。
3. 计算该子区间内所有元素到中位数的绝对差值之和。
4. 比较所有区间的代价，输出最小值。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功