题意ref{:target=”_blank”}
贪心算法,排序后,每次选择最小的2个数作为一个group
主要是证明方法:
假设序列 a,b,c,d,e,f
假设选择(a,c)是最优解法,我们证明如果选择(a,b)可以得到比最优解更好的结果即可
选择(a,c), min(a,c) = a; 剩余序列 (b,d,e,f);
选择(a,b), min(a,b) = a; 剩余序列 (c,d,e,f);
在剩余序列中,我们只考虑差异部分,假设(d,e,f...)相同的部分已经组成了一个最优解
由于 b<c<...,因此 (b,x) < (c,x)。
可以得知我们的贪心解法肯定会得到一个比最优解更好的解法,所以贪心的方法就是最优解
C++ 代码
class Solution {
public:
int arrayPairSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int res = 0;
for(int i=0; i<nums.size(); i+=2) {
res += nums[i];
}
return res;
}
};