LeetCode 561.Array Partition I

Description:

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:

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).

分析：

这道题很简单，当然不考虑时间复杂度的情况下，我们直接给vector按从小到大排序，然后从小到大每两个数取最小的那一个，显然加起来就是结果。

代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
	int arrayPairSum(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		int n = nums.size();
		int sum = 0;
		for (int i = 0; i < n; i += 2) {
			cout << min(nums[i], nums[i + 1]) << endl;
			sum += min(nums[i], nums[i + 1]);
		}
		return sum;
	}
};
int main() {
	Solution s;
	int n;
	cin >> n;
	vector<int> nums(n * 2);
	for (int i = 0; i < n * 2; i++) {
		cin >> nums[i];
	}
	cout << s.arrayPairSum(nums) << endl;
	return 0;
}