【LeetCode】561. Array Partition I
文章目录
题目描述
Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
Example 1:
Input: [1,4,3,2]
Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).
Note:
n is a positive integer, which is in the range of [1, 10000].
All the integers in the array will be in the range of [-10000, 10000].
解决方案
class Solution {
public:
int arrayPairSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<int>::iterator iter;
int sum = 0;
for( iter = nums.begin(); iter != nums.end(); iter+=2 )
{
sum += (*iter);
}
return sum;
}
};
解题思路
排序,按小到大顺序组合,取第一个数相加。
证明 from@shawngao
1. Assume in each pair i, bi >= ai.
2. Denote Sm = min(a1, b1) + min(a2, b2) + ... + min(an, bn). The
biggest Sm is the answer of this problem. Given 1, Sm = a1 + a2 +
... + an.
3. Denote Sa = a1 + b1 + a2 + b2 + ... + an + bn. Sa is constant for a
given input.
4. Denote di = |ai - bi|. Given 1, di = bi - ai. Denote Sd = d1 + d2 +
... + dn.
5. So Sa = a1 + a1 + d1 + a2 + a2 + d2 + ... + an + an + di = 2Sm + Sd
=> Sm = (Sa - Sd) / 2. To get the max Sm, given Sa is constant, we need to make Sd as small as possible.
6. So this problem becomes finding pairs in an array that makes sum of
di (distance between ai and bi) as small as possible.
7. Apparently, sum of these distances of adjacent elements is the
smallest. If that's not intuitive enough, see attached picture. Case
1 has the smallest Sd.
Submission Details
81 / 81 test cases passed.
Status: Accepted
Runtime: 89 ms

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论