用c++写代码:题目描述 春暖花开,实验室集体去长风公园泛舟。 实验室有 n(1<=N<=2000) 个人,每个人重量为 ci. 长风公园的每艘船的载重量为 K, 每次最多乘两人。假设每个人只能坐一次船,那么至少需要多少艘船才能让实验室全体都泛舟一次 ? 输入 输入第一行 T (1<=T<=30) 表示测试数据组数。 接下来有 T 组测试数据。 对于每组测试数据。 第一行有两个整数 N,K. N 表示实验室总人数 (3<=N<=2000),K(1<=K<=1000) 表示每艘船的最大载重量 第二行有 n 个整数 ci(1<=ci<=K ) 输出 对于每组测试数据输出一行,每行只有一个数字,即为最少的泛舟次数。
时间: 2024-03-05 15:51:42 浏览: 29
以下是使用贪心算法来解决这个问题的C++代码:
```c++
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 2005;
int c[MAXN];
int main()
{
int T;
cin >> T;
while (T--)
{
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++)
cin >> c[i];
sort(c, c + n); // 对人的重量排序
int ans = 0;
int left = 0, right = n - 1;
while (left <= right)
{
if (c[left] + c[right] <= k) // 两个人的重量加起来不超过k,可以坐同一艘船
left++;
right--;
ans++; // 无论是单独还是双人乘船,每次都需要增加一艘船的数量
}
cout << ans << endl;
}
return 0;
}
```
该算法的时间复杂度为O(NlogN),其中N为人的数量。该算法的核心思想是将人的重量按照从小到大的顺序排序,然后每次选择两个最重的人坐同一艘船,如果两个人的重量加起来超过了k,则只能让一个人坐船,船数加1。重复上述过程直到所有人都坐船为止。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)