基于贪心算法的2n只袜子配对算法设计问询

嘿，这个袜子配对求最小总惩罚的问题，用贪心算法就能完美解决，我给你一步步讲清楚：

核心思路 #

要让所有配对的总惩罚最小，最直观也最有效的贪心策略就是：把颜色最接近的袜子两两配对。毕竟如果硬把两个颜色相近的袜子拆开，分别和颜色更远的袜子配对，总惩罚只会变大不会变小。

具体算法步骤 #

• 第一步：把所有袜子的颜色按从小到大的顺序排序，得到有序序列：c₁ ≤ c₂ ≤ ... ≤ c_{2n}（这里的c_i是第i只袜子的颜色值）
• 第二步：直接将相邻的袜子两两配对，生成配对集合 A = {(c₁,c₂), (c₃,c₄), ..., (c_{2n-1},c_{2n})}
• 第三步：返回这个配对集合A即可

为什么这个贪心策略是最优的？ #

咱们用交换论证来证明它的最优性：
假设存在一个最优配对方案，其中有两组配对不是相邻的，比如配对了(c_i,c_j)和(c_k,c_l)，且满足i < k < j < l（因为序列已经排序，所以c_i ≤ c_k ≤ c_j ≤ c_l）。
现在我们把这两对换成(c_i,c_k)和(c_j,c_l)，计算总惩罚的变化：

• 原惩罚：|c_i - c_j| + |c_k - c_l| = (c_j - c_i) + (c_l - c_k)
• 新惩罚：|c_i - c_k| + |c_j - c_l| = (c_k - c_i) + (c_l - c_j)
  两者的差值为：(c_j - c_i + c_l - c_k) - (c_k - c_i + c_l - c_j) = 2(c_j - c_k) ≥ 0
  这说明新的配对方案总惩罚要么更小，要么和原来相等。也就是说，任何非相邻的配对都可以通过交换变成相邻配对，且总惩罚不会增加。由此可以推导出，相邻配对的贪心策略一定能得到最优解。

示例验证 #

比如有6只袜子，颜色分别是[1,3,4,5,7,8]，排序后就是原序列。
按照贪心算法配对：(1,3)惩罚2，(4,5)惩罚1，(7,8)惩罚1，总惩罚为4。
如果换成其他配对方式，比如(1,4)、(3,5)、(7,8)，总惩罚就是3+2+1=6，明显比贪心方案的惩罚大，完美验证了算法的正确性。

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