Greedy/881.Boats-to-Save-People/Readme.md
容易想到比较严谨的贪心解，就是找到当前最重的小胖x，然后找到当前最大的小瘦y使得x+y<=limit，这样x和y的配对是对资源的最优利用。
事实上这个贪心法可以进行松弛：对于当前最重的小胖x，只需要找到当前最小的小瘦y进行配对，就可以实现对资源的最优利用。分析如下。假设我们将所有人从轻到重排序y1,y2,y3,y4,...,x4,x3,x2,x1。对于当前最重的小胖对应的是x1，假设如果根据严谨的贪心算法找到的配对是y4（也就是恰好满足y4+x1<=limit），那么容易证明{x1,y1},{x2,y2},{x3,y3},{x4,y4}这四对其实都满足条件（即两个人加起来不超过limit）。所以我们可以将这四对剥离（因为已经充分利用了资源），对于剩下的人同理进行递归处理就可以了。
于是这道题就转化为了双指针。左右指针朝中间移动，计算有多少对满足people[i]+people[j]<=limit.
这种解法最大的隐患是时间复杂度需要O(NlogN)，勉强可以通过。
如何避免排序就能确定最重的人是谁呢？我们可以借鉴桶排序的思想：用一个计数器数组p来记录每个重量的人数。
假设当前最重的小胖的体重是x，那么对于x的值我们可以从limit开始往下猜，一旦发现p[x]>0，说明我们找到了这个最重的人。那么如何寻找x的最合理队友呢？我们可以从体重y=limit-x开始往下猜，一旦发现p[y]>0，就说明我们找到了最适合与x配对的小瘦（其体重为y）。记得每次配对之后，我们都需要及时更新计数器p[x]-- and/or p[y]--.
这种解法最大的雷区在于：如果遇到了x==y的情况，说明小胖和小瘦的体重相同，那么对于小胖的处理次数就不是原先的p[x]了，而是需要及时减去一才对。
可以将解法1的松弛贪心思想，以及解法2桶排序的思想结合起来。基本思想依然是双指针，但指针指的不是数组首尾的index，而是区间范围[1,limit]左右边界的value.
假设当前最重的小胖的体重是x，那么对于x的值我们可以从limit开始往下猜，一旦发现p[x]>0，说明我们找到了这个最重的人。同时我们寻找当前最轻的小瘦，假设其体重为y，对于y的值我们可以从1开始往上猜，一旦发现p[y]>0，说明我们找到了当前最轻的人。对于每个小胖我们都试图寻找当前最轻的小瘦，如果符合x+y<0 && p[y]>0就说明存在它可以与小胖同船。
显然容易分析出时间复杂度是o(N+limit)，比解法1要优秀.