求助：无法求解两个自然数集合元素配对的最优代价

最小绝对差之和 #

• 对集合A和B分别进行升序排序
• 将排序后的A的第i个元素与排序后的B的第i个元素一一配对，此时计算得到的绝对差之和是所有可能配对中的最小值

原理（交换论证） #

假设存在一组配对中，有两个元素对：(a₁, b₂) 和 (a₂, b₁)，其中a₁ < a₂，b₁ < b₂。对比两种配对方式的代价：

|a₁ - b₂| + |a₂ - b₁| vs |a₁ - b₁| + |a₂ - b₂|

展开后可证明后者的代价更小，因此任何不按对应排序配对的方案，都可以通过交换调整为对应排序配对，从而得到更小的代价。

最大绝对差之和 #

• 将集合A按升序排序，集合B按降序排序
• 将排序后的A的第i个元素与排序后的B的第i个元素一一配对，此时计算得到的绝对差之和是所有可能配对中的最大值

原理（交换论证） #

类似最小和的逻辑，假设存在一组配对中，有两个元素对：(a₁, b₁) 和 (a₂, b₂)，其中a₁ < a₂，b₁ < b₂。对比交换后的配对(a₁, b₂)和(a₂, b₁)的代价，可证明交换后的代价更大，因此按升序-降序对应配对能得到最大代价。

示例 #

假设A = [1, 4, 5], B = [2, 3, 6]

• 最小和（升序对应）：|1-2| + |4-3| + |5-6| = 1 + 1 + 1 = 3
• 最大和（A升序+B降序）：|1-6| + |4-3| + |5-2| =5 +1 +3=9

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