平方差之和最大化问题：集合元素排列策略问询

嘿，这个问题问得很精准！先直接给你结论：你想到的将A升序排序、B降序排序后配对的贪心策略，不仅没问题，而且是经过数学证明的最优解法，不存在遗漏的技巧哦。

为什么这个策略是对的？ #

我们可以从平方差和的展开式入手分析：
平方差和的公式为：
Σ(aᵢ - bᵢ)² = Σaᵢ² + Σbᵢ² - 2Σaᵢbᵢ
其中：

• Σaᵢ² 和 Σbᵢ² 是固定值，不管怎么排列集合元素，这两个总和都不会变
• 因此，要让平方差和最大化，核心就是要让 Σaᵢbᵢ（对应元素的乘积和）最小化

这时候就用到了经典的排序不等式：

对于两个有序数组，反序相乘的乘积和是所有配对方式中最小的；正序相乘的乘积和则是最大的。

把A升序排列、B降序排列，正好是反序配对，此时的乘积和Σaᵢbᵢ最小，代入公式后平方差和自然就是最大的。

举个直观例子验证 #

比如A={1,3,5}，B={2,4,6}：

• 反序配对（A升序，B降序）：(1-6)²+(3-4)²+(5-2)² = 25+1+9=35
• 正序配对：(1-2)²+(3-4)²+(5-6)²=1+1+1=3
• 随机配对：(1-4)²+(3-6)²+(5-2)²=9+9+9=27

很明显，反序配对的结果是最大的，完全符合预期。

特殊情况说明 #

哪怕集合里有重复元素，这个策略依然有效。比如A={2,2,3}，B={1,2,2}：
反序配对（A升序[2,2,3]，B降序[2,2,1]）：(2-2)²+(2-2)²+(3-1)²=0+0+4=4，这是所有配对里的最大值。

所以放心用这个策略就好，它就是最优解，没有隐藏的技巧需要补充啦。

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