-
Notifications
You must be signed in to change notification settings - Fork 0
/
47.过河问题.cpp
85 lines (75 loc) · 2.49 KB
/
47.过河问题.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/*
过河问题
时间限制: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
*/
/*
n==1 或者 n==2,所有人直接过河即可;
如果n==3,用时最短的和用时最长的一起过去,然后用时最短的回来,再和剩下的一个人过去 ;
如果n>=4,设a[0]表示用时最短的人所用的时间,a[1]为用时第二短的人所用的时间,a[n-1]表示用时
最长的人所用的时间,a[n-2]表示用时第二长的人所用的时间。那么:
当2a[1] + a[0] + a[n-1] > 2a[0] + a[n-1] + a[n-2]时,就先让用时最短的人和用时最长的人一起过去,
然后用时最短的回来,接着让用时最短的和用时第二长的一起过去,再让用时最短的回来。
否则,就先让用时最短的和用时第二短的一起过去,然后用时最短的回来,接着让用时最长和用时第二长的
一起过去,再让用时第二短的回来。这样就相当于剩下了n-2个人。对这n-2个人执行相同的操作,直到剩下
不足4个人即可直接结算所需的时间.
参考: http://blog.csdn.net/lyhvoyage/article/details/23196933
可以看出, 整个过程中一直都是最快和第二快的两个人把手电筒带回来, 只不过到底两次都是最快的人
把手电筒带回来还是一次由最快的带回来,一次由第二快的带回来, 要看上述的两趟送人加两趟带手电筒
回来的总时间那一个更少.
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[1005];
int main(){
#ifdef WFX
freopen("in.txt","r",stdin) ;
#endif
int T,n;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=0; i<n; ++i) scanf("%d",a+i);
sort(a,a+n);
int sum = 0;
while(n >= 4){
if(2*a[0] + a[n-1] + a[n-2] <= 2*a[1] + a[0] + a[n-1]){
sum += a[n-1]; //最快的和最慢的一起过桥
sum += a[0]; //最快的把手电筒带回来
sum += a[n-2]; //最快的和第二慢的一起过桥
sum += a[0]; //最快的把手电筒带回来
}else{
sum += a[1]; //最快的和第二快的一起过桥
sum += a[0]; //最快的把手电筒带回来(第二快的留在另一边,等会儿把手电筒带回来)
sum += a[n-1]; //最慢的和第二慢的一起过桥
sum += a[1]; //第二快的现在把手电筒带回来
}
n -= 2;
}
if(n==3) sum += a[0] + a[1] + a[2];
else if(n==2) sum += a[1];
else if(n==1) sum += a[0];
printf("%d\n",sum);
}
return 0;
}