C++代码实现:卡卡西和小朋友们要乘船过河了,港口有很多条船可以租到,并且之间没有区别,每条船的出租费用也是一样的。但是一条船最多只能乘坐两个人,且乘客的总重量不能超过船的最大承载量。我们要找出可以安置所有小朋友的最小船数以降低总的租船费用,卡卡西很快的写出了一个程序,读入船的最大承载量、旅客数目和每位旅客的重量,计算出要安置所有同学必须的最少的船的数目。
时间: 2023-12-03 21:43:40 浏览: 42
以下是C++代码实现:
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n, w, cnt = 0;
cin >> n >> w; // n表示旅客数目,w表示船的最大承载量
int *p = new int[n];
for(int i = 0; i < n; i++)
{
cin >> p[i];
}
sort(p, p+n); // 将旅客的重量从小到大排序
int i = 0, j = n-1;
while(i <= j) // 双指针扫描
{
if(p[i] + p[j] <= w) // 如果两个人的重量之和不超过船的最大承载量
{
i++;
j--;
}
else // 否则只能让一个人乘船
{
j--;
}
cnt++; // 记录乘船次数
}
cout << cnt << endl;
delete[] p;
return 0;
}
```
这里使用了双指针法,将旅客的重量从小到大排序后,使用两个指针从旅客数组两端开始扫描,每次找出两个重量之和不超过船的最大承载量的旅客,让他们一起乘船,否则只能让一个人乘船。最后记录下乘船的次数即可。