人群相邻就坐最少跳跃问题：贪心中位数策略的数学证明

题目基础信息 #

• 原题名称：Minimum jumps required to make a group of persons sit together（一组人相邻就坐所需的最少跳跃次数）
• 题目描述：给定长度为N、由x和.两种字符构成的字符串S表示一整排座位，其中x代表对应座位已被占用，.代表对应座位为空。计算让所有已就坐人员彼此相邻、中间无任何空座位时，需要的最少总跳跃（移动）步数。
• 题目示例：
  • 示例1：输入S = "....x..xx...x.."，输出结果为5。解释：将第5个座位上的人向右移动2步到第7个座位，将第13个座位上的人向左移动3步到第10个座位，总跳跃步数为2+3=5。
  • 示例2：输入S = "xxx..........xxxxxx"，输出结果为24。解释：将第1、2、3号座位上的人员分别移动到第9、10、11号座位，总跳跃步数为(9-1)+(10-2)+(11-3)=24。

核心疑问 #

目前通用的贪心解法为：将所有人员向已就座人群的中位数（中心位置的人员）方向移动，即可得到最小总跳跃步数，但该解法缺少严谨的推导证明，需要验证该策略的正确性。

策略正确性的严谨证明 #

我们可以通过坐标转换把原问题归约到经典的最小绝对值距离和问题，整个推导无额外假设：

1. 首先从左到右遍历座位字符串，提取所有坐了人的位置下标，得到长度为k的位置数组pos，其中pos[i]就是第i个人（从左往右计数）的初始座位编号，总共有k个人需要调整位置。
2. 当所有人调整为相邻就坐时，最终的座位一定是连续的k个位置。假设调整后最左侧的人的座位号是start，那么第i个人的最终座位号一定是start + i——相邻人之间没有空座，位置差恒为1。
3. 此时总移动步数就是每个人初始位置和最终位置的差的绝对值之和，可以展开写为：

   总步数 = Σ|pos[i] - (start + i)| ，i从0到k-1
   

   把式子做简单变形，将i移到绝对值内部和pos[i]合并：

   总步数 = Σ|(pos[i] - i) - start|
   

   令conv[i] = pos[i] - i，总步数就变成了Σ|conv[i] - start|，问题被完全转化为：找一个整数start，使得数组conv中所有元素到start的绝对值距离之和最小。
4. 这是已被严格证明的经典结论：一维坐标轴上的点集中，能让所有点到目标点的绝对值距离之和最小的目标点，就是点集的中位数。
   这个结论的推导非常直观：
   • 如果选的目标点在中位数左侧，此时目标点右侧的点数量比左侧多，把目标点往右挪1单位，所有右侧点到目标点的距离减1，所有左侧点到目标点的距离加1，总距离一定会变小。
   • 如果选的目标点在中位数右侧，此时目标点左侧的点数量比右侧多，把目标点往左挪1单位，总距离同样会变小。
   • 只有当目标点落在中位数位置时，不管往哪个方向移动，总距离都不会再下降，此时取到全局最小值。
5. 回到原问题的贪心策略：选中位数位置的人作为聚集中心，本质上就是让start取到conv数组的中位数对应的最优值，此时计算出来的总步数自然是全局最小值，不存在更优的聚集点选择。

注：不要把中位数和平均值搞混，平均值是最小化平方距离和的最优解，对于绝对值距离和的场景，平均值得到的结果一定大于等于中位数的结果。

内容的提问来源于stack exchange，提问作者Aayush