leetcode 881. Boats to Save People 救生艇

Problem: 881. Boats to Save People 救生艇

解题过程

排序，然后查找可以配对的，而且右上界是不断缩小的，用到了状态数组

优化版本只需要求出可以配对的，然后总数减去配对数量

Code

class Solution { public: int numRescueBoats(vector<int>& people, int limit) { sort(people.begin(), people.end()); int n = people.size(), l = 0, r = n - 1, sum = 0; vector<bool> status(n, false); while(l < n) { for(int i = r; i > l; i--) { if(status[i]==false && people[i] + people[l] <= limit) { status[i] = true; r = i - 1; break; } } status[l] = true; while(l < n && status[++l]==true) { } sum++; } return sum; } };

优化版本的

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