leetcode-561.Array Partition I

2017-05-08

最近总感觉自己越来越像码农，接触的东西一多就只注重怎么用，却无暇深究原理了。这和我的理想并不同，虽然我从来不认为自己是什么聪明人，尽管可能13级集训队的人当中，不得不说，和别人比，如今我混的简直不像人了–jc去了阿里，ysj搞大二就搞linux，如今我还玩不明白。。ff银牌拿到手软，那时候有zyh还当了几天队友，如今人家也考到中科院了，当年一起的学长学姐也都跑fdu了。
但人总要有点理想的，以前也搞过codeforce，想想当年半夜起来打比赛也是很醉人。刚才去codeforce上瞄了一眼，如今依旧是tourist统治rank，这货真的神牛。。正题，感觉最近要面试了，准备拿起leetcode刷一刷。

题目链接：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.

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

题意：给2n个数，2个数为一对，分成n对，n*(ai,bi),每对数取最小值，求n对数的和，保证和最大。

有点绕，不过题意还挺好理解，个人思想是排序(升序)后,取奇数和即可。尽量让最小数和次小数结合，因为我们要求总和最大，对于(ai,bi),假如ai为最小的数，那么bi尽量的小，才会满足如上策略，如果bi为大的数，就会被”喝”掉.这个喝字，是我们那的方言。。意思应该是被牺牲掉。
c++代码：

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int ans = 0;
        for(int i = 0; i < nums.size(); i+=2) {
            ans += nums[i];
        }
        return ans;
    }
};

跑完发现runtime超过了2%的人。。真提莫的丢人