LEETCODE ALGORITHM:881. Boats to Save People

发表于 更新于 分类于 Waline： 阅读次数：

题目

The i-th person has weight people[i], and each boat can carry a maximum weight of limit.

Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person. (It is guaranteed each person can be carried by a boat.)

Example 1:

1
2
3
Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)

Example 2:

1
2
3
Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)

Example 3:

1
2
3
Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)

Note:

  • 1 <= people.length <= 50000
  • 1 <= people[i] <= limit <= 30000

题解

贪心：让体重最大的和体重最小的一起乘船，如果体重超过限制让体重大的肚子撑船

可能会有疑问，贪心不应该尽量保证每个船上人的重量尽量大，如果有体重为5 4 3 2 1的5个人，限制为7，应该让体重分别为5和2的人同坐，且不是上面算法中的5和1同坐。这种想法没有问题，也可以得出正确答案，但是会增加时间复杂度。因为一个船只能做两个人，2能和最重的人同坐一艘船，也就表示他可以和任何人同坐一艘船，并不存在找不到同伴（除非奇数个人）的问题，所以并不需要一定重量最大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(),people.end(),greater<int>());
        int i=0,j=people.size()-1,ans=0;
        while(i<=j)
        {
            if(people[i]+people[j]<=limit)
            {
                ++i;--j;
            }else{
                ++i;
            }
            ++ans;
        }
        return ans;
    }
};