过河问题
KB
- 描述
-
在
漆黑的夜里,N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话,大家是无论如何也不敢过桥去的。不幸的是,N个人一共只带了一只手电
筒,而桥窄得只够让两个人同时过。如果各自单独过桥的话,N人所需要的时间已知;而如果两人同时过桥,所需要的时间就是走得比较慢的那个人单独行动时所需
的时间。问题是,如何设计一个方案,让这N人尽快过桥。
简化模型到最后
然后对于每次过河回来的人应该是河对岸的过河速度最快的人
很自然的想到
但是当n=4的时候
接下来我们要确认是否还有特殊情况,先思考当有n个人过河,
import java.util.Arrays;
import java.util.Scanner;
//acm_47
public class PassRiver {
static void main(String[] args) {
PassRiver passRiver = new PassRiver();
passRiver.solution();
solution() {
Scanner(System.in);
in.nextInt();
0; i < groups; i++) {
getDate();
System.out.println(handle(num));
in;
num;
int[]
getDate(){
in.nextInt();
int[num];
0 ; i < timer.length;i++){
in.nextInt();
Arrays.sort(timer);
//这里的逻辑是对数据进行处理,准备采用递归的方法,穿进去的是剩余的人数
handle(int index){
switch(index){
case 1:
case 2:
case 3:
timer[0]+timer[1]+timer[2];
}
return Math.min(timer[0]+timer[index-2],
2*timer[1])+timer[index-1]+timer[0] + handle(index-2);
}