算法
程序员文章站
2022-07-16 08:02:46
...
这个题目的要求是给定一个数组,有2N个元素,将其划分为N对(每一对有两个元素),使得每一对中的最小的元素相加的总和最大,例如:
有一个数组:
s=a1+b1+a2+b2+a3+b(3)+…+an+bn;
我们的目标是将数组划分诸如:
(a1,b1),(a2,b2),(a3,b3),….(an,bn)
然后求:
Sm = min(a1, b1) + min(a2, b2) + … + min(an, bn)
假设对于每一组bi>=ai,Sm(Sm = a1 + a2 + … + an)的最大值就是我们的目标.
定义
1、Sa = a1 + b1 + a2 + b2 + … + an + bn,对于输入的数组来说Sa是一个常数;
2、di = |ai - bi|,Sd = d1 + d2 + … + dn
所以我们可以得到Sa=a1 + a1 + d1 + a2 + a2 + d2 + … + an + an + di = 2Sm + Sd => Sm = (Sa - Sd) / 2
因为Sa是一个常量,要使得Sm最大的话,我们就要使得Sd最小。
一个数组中如何求的Sd最小呢,假如这个数组是一个已排序的数组:
(a1<=b1<=a2<=b2,那么Sd=(b1-a1)+(b2-a2),下图形象地说明了这点:
代码实现:
public int arrayPairSum(int[] nums) {
Arrays.sort(nums);
int result = 0;
for (int i = 0; i < nums.length; i += 2) {
result += nums[i];
}
return result;
}