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