C++代码实现贪心做法:卡卡西和小朋友们要乘船过河了,港口有很多条船可以租到,并且之间没有区别,每条船的出租费用也是一样的。但是一条船最多只能乘坐两个人,且乘客的总重量不能超过船的最大承载量。我们要找出可以安置所有小朋友的最小船数以降低总的租船费用,卡卡西很快的写出了一个程序,读入船的最大承载量、旅客数目和每位旅客的重量,计算出要安置所有同学必须的最少的船的数目。
时间: 2023-12-03 18:43:42 浏览: 43
以下是C++代码实现:
```c++
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1000;
int n, w, ans, a[MAXN+5];
int main(){
cin >> n >> w;
for(int i=1;i<=n;i++)
cin >> a[i];
sort(a+1, a+n+1);//将旅客重量从小到大排序
int l = 1, r = n; //双指针
while(l<=r){
if(a[l]+a[r]<=w) l++;
r--;
ans++; //每次安排一艘船
}
cout << ans << endl;
return 0;
}
```
代码思路:
1. 首先读入船的最大承载量和旅客数目。
2. 然后读入每位旅客的重量,将其从小到大排序。
3. 使用双指针进行贪心,每次选择两个最重的旅客。
4. 如果这两个旅客的总重量不超过船的最大承载量,则安排他们乘坐一艘船。
5. 如果超过了船的最大承载量,则只能让一个旅客乘坐一艘船。
6. 重复步骤4、5,直到所有旅客都安排上船。
7. 最后输出安排的船的数量即为答案。