最小向量积

2018-11-08 本文已影响0人 M_lear

调整数组元素的位置使得两数组向量积最小

有长度为n的数组a，b，问如何调整数组内元素的位置使得 $a\cdot b$ 最小？

对应小的乘大的，大的乘小的，得到的向量积最小。

重定义a的逆序
依据数组b来定义数组a的逆序，假设有a，b对应位置上的两对数 $a_{i},a_{j}$ 和 $b_{i},b_{j}$ ，如果有 $b_{i}<b_{j}$ 时 $a_{i}>a_{j}$ ，或者 $b_{i}>b_{j}$ 时 $a_{i}<a_{j}$ ，则称 $a_{i},a_{j}$ 为一对逆序，否则不为逆序。
证明单调
假设现在有 $b_{i}<b_{j}$ ， $a_{i}<a_{j}$ ， $i=0,1,\cdots,n-1$ ， $j=0,1,\cdots,n-1$ ， $i\ne j$
则向量积 $S_{1}=\sum_{k=0,k\ne i,k\ne j}^{n-1}a_{k}\cdot b_{k}+a_{i}\cdot b_{i}+a_{j}\cdot b_{j}$
若现在交换 $a_{i},a_{j}$ 的位置，即数组a增加了一对逆序。
向量积变为 $S_{2}=\sum_{k=0,k\ne i,k\ne j}^{n-1}a_{k}\cdot b_{k}+a_{i}\cdot b_{j}+a_{j}\cdot b_{i}$
可以证得 $a_{i}\cdot b_{i}+a_{j}\cdot b_{j}>a_{i}\cdot b_{j}+a_{j}\cdot b_{i}$ （这个简单证明放在第3点）
即 $S_{1}>S_{2}$
所以结论是：保持b不变，a每增加一对逆序，a，b的向量积就一定会变小，两者呈反比。

所以当a是相对于b的全逆序时，a，b的向量积最小。相反的，当a是相对于b的全顺序时，a，b的向量积最大。

下面证明 $a_{i}\cdot b_{i}+a_{j}\cdot b_{j}>a_{i}\cdot b_{j}+a_{j}\cdot b_{i}$ ：
因为 $b_{i}<b_{j}$ ， $a_{i}<a_{j}$ ，所以 $b_{i}-b_{j}<0$ ， $a_{i}-a_{j}<0$
即 $(a_{i}-a_{j})\cdot(b_{i}-b_{j})>0$
对上式展开移项即可得到要证明的结论。