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