救生艇..

本节解决一个救生艇人员问题,即在每搜救生艇承重有限的情况下,需要多少艘救生艇才能容纳所有人.

问题描述:

第i个人的重量为people[i],每搜救生艇最大承载重量为weight,每艘救生艇最多可同时承载两个人,但条件是这些人的重量之和不大于weight.要每个人都有救生艇坐,求至少需要多少救生艇.

思路解析:

根据题目,一艘救生艇做多容纳两个人,十分明显的,应先将体重的数组从小到大排列,让后双指针分别指向第一个人和最后一个人,通过不断判断指针所指的两个人是否可以同坐一艘救生艇来不断计算所需救生艇数量,同时移动两个指针,直到两指针相遇.变量如下:

people变量:表示输入所有人重量的数组

weight变量:表示每艘救生艇所能容纳的最大重量

left变量:表示左指针,起始指向最轻的人

right变量:表示右指针,初始指向最重的人

res变量:表示最终返回的救生艇数量

完整代码如下:

def RescueBoats(self, people, weight):
    # 将人们按照体重从小到大排序
    people.sort()
    
    # 初始化两个指针，left指向最轻的人（数组的开始），right指向最重的人（数组的末尾）
    left = 0
    right = len(people) - 1
    
    # 初始化所需船只数量为0
    res = 0
    
    # 当left指针小于等于right指针时，循环继续
    while left <= right:
        # 每进入一次循环，代表使用了一条船，所以船的数量加1
        res += 1
        
        # 如果最轻的人和最重的人的体重之和不超过船的载重限制
        if people[left] + people[right] <= weight:
            # 将left指针向右移动一位，即考虑下一个体重更重的人
            left += 1
        # 不论是否能够将最轻和最重的人配对，都将right指针向左移动一位，即考虑下一个体重更轻的人
        right -= 1
    
    # 返回所需的船只数量
    return res