最近总感觉自己越来越像码农,接触的东西一多就只注重怎么用,却无暇深究原理了。这和我的理想并不同,虽然我从来不认为自己是什么聪明人,尽管可能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++代码:
1 | class Solution { |
跑完发现runtime超过了2%的人。。真提莫的丢人