数组拆分-力扣561-C++

一、题目描述 

给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。

返回该 最大总和 。

示例 1：

输入：nums = [1,4,3,2]
输出：4
解释：所有可能的分法（忽略元素顺序）为：
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
所以最大总和为 4

示例 2：

输入：nums = [6,2,6,5,1,2]
输出：9
解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/array-partition

二、运行结果

 

三、求解思路

本题最核心的问题在于哪些数作为数对(a, b)中的的较小值时，取出的最小值之和最大。可以从以下角度考虑：

1）假定数组中的数从小到大排序为：a1, a2, a3, …… an;

2）an为最大的数，显然不可能作为数对(a, b)中的较小值，那取a(n-1)作为其中的数对的较小值时可以使得最终的结果更大，依次类推，第三大的数(a(n-2))不可能作为数对中的较小值，那就取第四大的数(a(n-3))作为其中的较小值……

3）可以看出，要使得数对中的较小值之和最大，n个数对中取出的较小值分别是a(n-2), a(n-4)……a0，即对于排序好的数组，从最小值开始，隔一个数取一个值求和，可以得到所求的结果。

四、代码

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        int len = nums.size();
        sort(nums.begin(), nums.end());  //对原数组进行排序
        int ans = 0;
        for(int i=0; i2) //隔一个元素取一个
        {
            ans += nums[i];
        }
        return ans;
    }
};