经典算法题之过桥问题

发表于 | 分类于 ，

　　最近做笔试题碰到了一道经典的算法题：旅行者过桥问题。想起之前在笔试的过程中也碰到了这道题，于是决定整理一下。

问题

　　在漆黑的夜里，N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，N个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，N人所需要的时间已知；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这N人尽快过桥。假设N <= 1000。

思路

　　拿到此题的第一个想法肯定是贪心，但整个贪心的具体过程确并不简单。设最快的两个人过桥所需的时间为A、B，最慢的两个人过桥所需的时间为X、Y。首先需要明白的是肯定要桥对面的过桥所需时间最小的人送电筒回来。我们考虑首先让最慢的两个人过桥，而让最慢的两个人过桥有两种情况。
　　情况一：让最快的人（A）送最慢的两个人过桥：首先让A与Y过桥，过桥所需时间为Y；然后让A送电筒回来，所需时间为A；然后让A与X过桥，所需时间为X；然后让A送电筒回来。此时X与Y都过了桥，所需总时长为：Y+A+X+A=2A+X+Y。
　　情况二：让最快的两个人（A和B）送最慢的两个人过桥：首先A与B过桥，所需时间为B；然后A送电筒回来，所需时间为A；然后让X和Y一起过桥，所需时间为Y；然后让B送电筒回来，所需时间为B。此时X与Y都过了桥，所需总时长为：B+A+Y+B=2B+Y。
　　在让最慢的两个人过桥的过程中，我们要取这两种情况的最小值计算。
　　同时边界情况为：只有三个时，总时长为三者时长之和；只有两个人时，总时长为用时较多的人的时长；只有1个人时，总时长即为这个人过桥所用时长。 　　

代码

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
package com.wh.problems.huya;

import java.util.Arrays;
import java.util.Scanner;

public class Bridge {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] time = new int[n];
		for(int i = 0;i < n;i++) {
			time[i] = sc.nextInt();
		}
		Arrays.sort(time);
		int minTime = 0;
		int i = n-1;
		for(;i > 2;i -= 2) {
			minTime += Math.min(2*time[0]+time[i-1]+time[i], time[0]+2*time[1]+time[i]);
		}
		if (i == 2) {
			minTime += time[0]+time[1]+time[2];
		}else if (i==1) {
			minTime += time[1];
		}else {
			minTime += time[0];
		}
		System.out.println(minTime);
	}
}

参考链接

https://www.jianshu.com/p/84608db757b4