题目描述
官方描述(中文)
2021/08/26每日一题
思路
排序+双指针
原则优先让剩下的最轻和最重的同学组队,如果最轻的都不能和最重的组队,那最重的只能自己乘船。
- 先把数组由大到小进行排序。
- 定义两个指针i,j。分别指向队首和队尾。
- v[i]+v[j]有两种情况
- v[i]+v[j]<=limit.nice,i,j可以同时接走了
- 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.