解题思路
首先猜想最终相等的元素t的范围，最终应为数组中的某个元素。
- 若
t小于数组中所有的元素，则此时增大t，那么所有元素变为t的次数将减小，可见t并非最优解； - 若
t大于数组中所有的元素，则此时减小t，那么所有元素变为t的次数将减小，可见t并非最优解；
可见t应该位于数组最大与最小值之间，下面证明最优的t可以取为数组中的某个元素，从而遍历数组元素即可。
如上图所示，设t为数组最大与最小值之间的一个值，若t不为数组中的某个元素，则设此时大于t的元素有x个，小于t的元素为y个。
若x>y，则上移一格t，此时操作数变化量为-x+y<0，将会更优；
若x<y，则下移一格t，此时操作数变化量为+x-y<0，将会更优；
若x=y，则无论上移与下移，操作数不变。
因此，可以看出若t不取数组中的某个元素值，则总可以通过调整t，使得操作数更少。因此t应该取数组中的某个值。
则问题转化为：
遍历数组中的数，找到某个元素t，使得t到其他元素值的距离之和最小。
由绝对值不等式可知，当t取数组中位数时，该距离之和最小。
中位数+绝对值不等式 \(AcWing\) \(104\). 货仓选址
排序之后取中位数,中位数的性质,所有数到他的和是最小的。
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1010;
int a[N];
int n, k;
int res = INF;
// 时间复杂度：10000*10000=1e8，C++一秒可过
/**
测试用例I:
3 2
3 6 1
答案
3
测试用例II:
4 2
2 6 11 18
答案：
4
解释：
将2调到6，需要4步。
也可以把2调到3，1步。
把6降到3，3步，共4步。
测试用例III:
5 3
2 6 11 18 14
答案：
7
解释：
将11调到14，需要3步
将18调到14，需要4步，共7步。
测试用例IV
5 3
1 2 7 8 12
答案：5
解释：
最终结果是8，
7+1=8，1步
8不需要动，0步
12-8=4，4步
共1+0+4=5步
*/
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n - k + 1; i++) { // 枚举起点
vector<int> b;
for (int j = i; j <= i + k - 1; j++) b.push_back(a[j]); // 将每个可用范围复制到数组b中
sort(b.begin(), b.end()); // 排序
int cnt = 0; // 变更次数
for (int j = 0; j < b.size(); j++) cnt += abs(b[b.size() / 2] - b[j]); // 枚举每个数字与中位数对比
res = min(res, cnt); // 记录最少变更次数
}
printf("%d\n", res);
return 0;
}