题目描述

官方描述(中文)
2021/08/26每日一题

思路

排序+双指针

原则优先让剩下的最轻和最重的同学组队，如果最轻的都不能和最重的组队，那最重的只能自己乘船。

1. 先把数组由大到小进行排序。
2. 定义两个指针i，j。分别指向队首和队尾。
3. v[i]+v[j]有两种情况
   1. v[i]+v[j]<=limit.nice，i，j可以同时接走了
   2. v[i]+v[j]>limit. 只能委屈j自己走了。

代码

class Solution 
{
public:
    int numRescueBoats(vector<int>& people, int limit) 
    {
        int res{0};
        sort(people.begin(), people.end());
        int i = 0, j = people.size()-1;
        while(i<=j && j>=0 && i<people.size()) 
        {
            if((people[i] + people[j--])<=limit)
                ++i;
            ++res;
        }
        return res;
    }
};

运行结果

Q.E.D.