数组差的绝对值
浏览数：42 /
时间：2015年06月08日
Given two arrays A, B with size n, you could justify the positions of number in array B to maximum the sum[abs(ai-bi)], i from 0 to n or minimize the sum[abs(ai-bi)].
---------------------------------------------------------------------
Maximum: sort all numbers in A and B, Use the last n numbers to minus the first n numbers.
Minimum: sort A and B separately. Use proof by contradiction:
Image Ai < Aj and Bi > Bj, discuss the6 situations:
Ai < Aj < Bi < Bj
Ai < Bi< Aj < Bj
Ai < Bi < Bj< Aj
Bi < Ai < Aj < Bj
Bi < Ai < Bj < Aj
Bi < Bj < Ai < Aj
In all of the situations , |Ai-Bi|+|Aj-Bj| <= |Ai-Bj|+|Aj-Bi|
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
