961
過河問題
過河問題
時間限製：1000 ms | 內存限製：65535 KB
難度：5
- 描述
-
在漆黑的夜裏，N位旅行者來到了一座狹窄而且沒有護欄的橋邊。如果不借助手電筒的話，大家是無論如何也不敢過橋去的。不幸的是，N個人一共隻帶了一隻手電筒，而橋窄得隻夠讓兩個人同時過。如果各自單獨過橋的話，N人所需要的時間已知；而如果兩人同時過橋，所需要的時間就是走得比較慢的那個人單獨行動時所需的時間。問題是，如何設計一個方案，讓這N人盡快過橋。
- 輸入
- 第一行是一個整數T(1<=T<=20)表示測試數據的組數
每組測試數據的第一行是一個整數N(1<=N<=1000)表示共有N個人要過河
每組測試數據的第二行是N個整數Si,表示此人過河所需要花時間。(0<Si<=100) - 輸出
- 輸出所有人都過河需要用的最少時間
- 樣例輸入
-
1 4 1 2 5 10
- 樣例輸出
-
17
過河方法：人數大於3時，
第一種可能快的方法是、：最快和次快的先過，最快的回來，然後最慢和次慢的過，然後讓次快的回來，直到人數小於等於3為止
第二種可能快的方法是、：每次都是最快的送最慢的過橋，最快的回來，再送剩餘人數中最慢的過，直到人數小於等於3為止。
查看代碼---運行號：252575----結果：Accepted
運行時間：2012-10-06 11:25:47 | 運行人:huangyibiao
01.#include <iostream>
02.#include <algorithm>
03.using
namespace std;
04.
05.int
main()
06.{
07.int
sample;
08.cin >> sample;
09.
10.while
(sample --)
11.{
12.int
nPeople;//人數
13.cin >> nPeople;
14.
15.int
*time
= new int[nPeople];
16.for
(int
i = 0; i < nPeople; i++)
17.cin >>
time[i];
18.
19.sort(time,
time+nPeople);//時間從小到大排序
20.
21.int
minTime = 0;
22.while
(nPeople > 3)
23.{
24.minTime += min(time[0] +
time[1] * 2 +
time[nPeople-1],
25.time[0] * 2 +
time[nPeople-2] +
time[nPeople-1]);
26.nPeople -= 2;
27.}
28.
29.if
(nPeople == 1)
30.{
31.minTime +=
time[0];
32.}
33.else
if (nPeople == 2)
34.{
35.minTime +=
time[1];
36.}
37.else
38.minTime +=
time[0] + time[1] +
time[2];
39.
40.cout << minTime << endl;
41.delete
[] time;
42.}
43.return
0;
44.}
最後更新：2017-04-02 15:14:53