644
独木舟上的旅行
独木舟上的旅行
时间限制：3000 ms | 内存限制：65535 KB
难度：2
- 描述
-
进行一次独木舟的旅行活动，独木舟可以在港口租到，并且之间没有区别。一条独木舟最多只能乘坐两个人，且乘客的总重量不能超过独木舟的最大承载量。我们要尽量减少这次活动中的花销，所以要找出可以安置所有旅客的最少的独木舟条数。现在请写一个程序，读入独木舟的最大承载量、旅客数目和每位旅客的重量。根据给出的规则，计算要安置所有旅客必须的最少的独木舟条数，并输出结果。
- 输入
- 第一行输入s,表示测试数据的组数；
每组数据的第一行包括两个整数w，n，80<=w<=200,1<=n<=300，w为一条独木舟的最大承载量,n为人数；
接下来的一组数据为每个人的重量（不能大于船的承载量）； - 输出
- 每组人数所需要的最少独木舟的条数。
- 样例输入
-
385 65 84 85 80 84 8390 390 45 60100 550 50 90 40 60
- 样例输出
-
533
查看代码---运行号：252535----结果：Accepted
运行时间：2012-10-06 09:22:25 | 运行人:huangyibiao
01.#include <iostream>
02.#include <cstdio>
03.#include <algorithm>
04.using
namespace std;
05.
06.int
main()
07.{
08.int
sample;
09.cin >> sample;
10.
11.while
(sample --)
12.{
13.int
nMaxWeight;//最大承载量
14.int
nNumOfPeople;//人数
15.
16.scanf("%d%d",
&nMaxWeight, &nNumOfPeople);
17.int
*weight = new
int[nNumOfPeople];
18.
19.for
(int
i = 0; i < nNumOfPeople; i++)
20.scanf("%d", &weight[i]);
21.
22.sort(weight, weight+nNumOfPeople);
//从小到大排序
23.
24.int
nCanoe = 0;//独木舟的数量
25.int
nLeft = nNumOfPeople;
26.int
begin = 0, end = nNumOfPeople-1;
27.while
(nLeft)//当没全部上独木舟时
28.{
29.if
(weight[begin] + weight[end] <= nMaxWeight)
30.{
31.nCanoe++;
32.begin ++;
33.end --;
34.nLeft -= 2;
35.}
36.else
37.end --;
38.
39.if
(begin >= end)//说明剩下的人中任意两个一起都超重
40.{
41.nCanoe += nLeft;//剩下的人，每人一个独木舟
42.nLeft = 0;
43.}
44.}
45.cout << nCanoe << endl;
46.
47.delete
[] weight;
48.}
49.return
0;
50.}
最后更新：2017-04-02 15:14:53