leetcode：881. 救生艇

题目来源

• leetcode：881. 救生艇

题目描述

class Solution {
    
public:
    int numRescueBoats(vector<int>& people, int limit) {
    

    }
};

题目解析

贪心+双指针

（1）先遍历一遍数组，如果有一个人的体重超过了limit，那么返回无穷大，表示多少条船都搞不定

（2）然后排序，从中间分界点开始往左右两边滑

• 找 <= limit/2最右边的位置，作为L指针
• 找第一个超过limit/2的位置，作为R指针
• 看L位置和R位置能否凑一个船，不能，超过

• L往左边移动…L来到了3，可以
  

• 先不分配船，R往右滑，一直滑到R再往下进一个就没有办法跟3凑一船为止

• 贪心的出发点：从3出发往左数6个，去消耗右边的这6个，一定是最省的

（3）举例：右边先耗尽

（4）举例：左侧先耗尽

$$船的数量=\frac{\times 数量}{2}+\frac{\surd 数量}{2}+右侧剩下的数量$$

class Solution {
    
public:
    int numRescueBoats(vector<int>& people, int limit) {
    
        if(people.empty()){
    
            return 0;
        }
        
        int N = people.size();
        std::sort(people.begin(), people.end());
        if(people[N - 1] > limit){
    
            return -1;
        }
        
        int lessR = -1;
        for (int i = N - 1; i >= 0; --i) {
    
            if(people[i] <= limit/2){
    
                lessR = i;
                break;
            }
        }
        
        if(lessR == -1){
    
            return N;
        }
        
        int L = lessR;
        int R = lessR + 1;
        int noUsed = 0;
        while (L >= 0){
    
            int solved = 0;
            while (R < N && people[L] + people[R] <= limit){
    
                solved++;
                R++;
            }
            if(solved == 0){
    
                noUsed++;
                L--;
            }else{
    
                L = std::max(-1, L - solved);
            }
        }
        int all = lessR + 1;
        int used = all - noUsed;
        int moreUnsolved = (N - all) - used;
        return used + ((noUsed + 1) >> 1) + moreUnsolved;
    }
};

首尾双指针

class Solution {
    
public:
    int numRescueBoats(vector<int>& people, int limit) {
    
        int N = people.size();
        std::sort(people.begin(), people.end());
        if(people[N - 1] > limit){
    
            return -1;
        }
        
        int ans = 0, l = 0, r = N - 1, sum = 0;
        while (l <= r){
    
            sum = l == r ? people[l] : people[l] + people[r];
            if(sum > limit){
    
                r--;
            }else{
    
                l++;
                r--;
            }
            ans++;
        }
        return ans;
    }
};