过河问题
时间限制：1000 ms | 内存限制：65535 KB
难度：5
描述
在漆黑的夜里，N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，N个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，N人所需要的时间已知；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这N人尽快过桥。
输入
第一行是一个整数T(1<=T<=20)表示测试数据的组数
每组测试数据的第一行是一个整数N(1<=N<=1000)表示共有N个人要过河
每组测试数据的第二行是N个整数Si,表示此人过河所需要花时间。(0<Si<=100)
输出
输出所有人都过河需要用的最少时间
样例输入
样例输出
这个题还是蛮有意思的，上图说话：
ac代码：
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
| import java.util.Arrays;
import java.util.Scanner;
public class T9过河问题 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
int[] out=new int[n];
for (int i = 0; i < out.length; i++) {
int t=sc.nextInt();
int[] data=new int[t];
for (int j = 0; j < data.length; j++) {
data[j]=sc.nextInt();
}
out[i]=f(data);
}
for (int i = 0; i < out.length; i++) {
System.out.println(out[i]);
}
}
}
private static int f(int[] data) {
Arrays.sort(data);//排序
int index=data.length-1;//数组下标
int ans=0; //最短过桥的和时间
int counts=data.length; //有多少人需要过河
if(counts==1){
return data[0];
}
//当人数大于等于四人时，可以采用两种方案运送最大的两个为一次行动
while(counts>=4){
int Min=data[0]; //用时最短的
int eMin=data[1]; //用时第二短的
int Max=data[index]; //用时最长的
int eMax=data[index-1];//用时第二长的
int sum1=eMin+Min+Max+eMin;//方案一：两小送两大的，用时：第二小+第一小+最大的+第二
int sum2=Max+Min+eMax+Min; //方案二：最小的分别送两大的，用时：最大的+最小的+第二大的+最小的
ans+=Math.min(sum1,sum2);//选择其中用时较短的一种方案
index-=2;//运送过去了两个人
counts-=2;
}
//最后还有三个人时，剩下三个相加
if(counts==3){
ans+=data[index]+data[0]+data[1];
}
//两个人时，用时为大的那个
if(counts==2){
ans+=data[1];
}
return ans;
}
}
|