漂流船问题
漂流船问题
https://www.nowcoder.com/practice/0e6cb06ec63148ed952f887a787f0103?tpId=98&tqId=32869&tPage=3&rp=3&ru=/ta/2019test&qru=/ta/2019test/question-ranking
题目难度：二星
考察点：贪心
方法：贪心
1.分析：
因为这个题一定要注意的是每艘船最多可同时载两人这个条件，那么其实我们首先需要要将读入进来的体重数组进行排序，然后我们在采用贪心的算法，将最重的人和最轻的人尽可能的放在一条船上，这样保证得到的船只数是最小的，那么我们就要判断最重的人和最轻的人是否能够在一条船上，即判断最重的人和最轻的人是否大于limit的值就可以了，如果最重的人和最轻的人是否大于limit，那么最重的人就可以和最轻的人在一条船上，否则最重的人就只能一个人一条船。在对体重数组排序完成后，我们可以采用双指针的方法来求解答案，即设置l=0， r=n-1，其中l表示较轻的人，r表示较重的人，然后满足条件while(l < r)，如果当前较轻的人和当前较重的人的体重加在一起，那么我们就能让这两个人在一条穿上，即两个指针都进行移动l++,r--，否则就只能较重的人一个人一条船，即指针r移动, r--。最后我们在判断指针l和r是否相等，如果相等，那么还得需要一条船来装这个人，至此这个题目就可以解决了。
例如：有4个人体重分别是1、2、 3、 5 船的载重为4。
初始化指针l=0, r=3, ans = 0：
第一次：a[0]+a[3] > 4， 那么此时 ans++, r--， 即ans=1， r= 2。
第二次：a[0]+a[2] == 4， 那么此时 ans++, l++, r--， 即ans=2， l = 1, r= 1。
第三次：l == r， 那么此时 ans++, 即ans = 3。
算法实现：
(1). 使用getline和stringstream处理一下输入，得到体重数组和limit值。(2). 将体重数组进行排序。
(3). 根据上述双指针进行计算结果，即如果(a[l] + a[r] <= limit) 那么指针l和r都进行移动，否则只移动指针r，而每次都需要对结果进行+1，因为无论是大于limit还是小于limit都需要一条船。
(4). 输出结果ans。
空间复杂度：O(n)
2.复杂度分析：
时间复杂度：O(n*log(n))空间复杂度：O(n)
3.代码：
#include <bits/stdc++.h>
using namespace std;
vector<int> a;
int main(){
string str; getline(cin, str);
stringstream ss(str);
int x; while(ss>>x) a.push_back(x);
int limit; cin>>limit;
sort(a.begin(), a.end());
int l = 0, r = a.size()-1, ans = 0;
while(l < r) {
if(a[l] + a[r] <= limit) l++, r--;
else r--;
ans++;
}
ans += (l == r);
cout<<ans<<endl;
return 0;
}
查看19道真题和解析
合合信息公司福利 271人发布
