最短时间过桥

本文用代码实现最短时间过桥，并且打印如下两个例子的最小过桥时间：

例子一：四人夜间过桥，他们只有一个手电筒一次只能两个人过桥，过桥时必须有手电筒，四人过桥时间为1分2分6分10分

例子二：小明过桥要一秒，小明的弟弟要三秒，小明的爸爸要六秒，小明的妈妈要八秒，小明的爷爷要十二秒。每次此桥最多可过两人，而过桥的速度，依过桥最慢者而定，可是灯在点燃后， 三十秒就会熄灭（过桥需要灯照明）。那么，请问小明一家，如何在三十秒内过桥？

代码：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author Eric
 */

public class CrossBridge {

	/**
	 * @param personSpeeds
	 *            每个人过桥所需时间的一个列表
	 */
	public void crossBridge(List<Integer> personSpeeds) {
		if (null == personSpeeds || 0 == personSpeeds.size()) {
			throw new IllegalArgumentException("至少有一个人需要过桥，请保证参数至少有一个元素。");
		} else if (!isSpeedParameterLeagal(personSpeeds)) {
			throw new IllegalArgumentException("请纠正过桥时间，每个人的过桥时间不能小于等于零。");
		} else if (1 == personSpeeds.size()) {
			// 只有一个人过桥,那么直接输出过桥过桥时间
			System.out.printf("%d -> Go \n", personSpeeds.get(0));
			System.out.printf("最少过桥耗时 %s 秒！\n", personSpeeds.get(0));
		} else if (2 == personSpeeds.size()) {
			// 只有两个人过桥,那么直接输出过桥过桥时间
			System.out.printf("%d %d -> Go \n", personSpeeds.get(0),
					personSpeeds.get(1));
			System.out.printf("最少过桥耗时 %d 秒！\n", personSpeeds.get(0)
					+ personSpeeds.get(0));
		} else {
			// 处理多个人过桥的场景

			// 为了获取过桥时间的最大最小值，首先对personSpeeds排序
			Collections.sort(personSpeeds);

			doBridgeCross(personSpeeds);
		}

	}

	private void doBridgeCross(List<Integer> personSpeeds) {
		List<Integer> source = new ArrayList<Integer>();
		source.addAll(personSpeeds);
		List<Integer> destination = new ArrayList<Integer>();
		int totalCrossBridgeTime = 0;
		boolean secondFastestOnDest = false;

		while (!source.isEmpty()) {
			int srcFastest = source.get(0);
			int srcSecondFastest = source.get(1);

			if (2 == source.size()) {
				totalCrossBridgeTime += populateBridgeCrossingTime(source,
						destination, srcFastest, srcSecondFastest, false);
			} else {
				// 处理多余两个人过桥的情况

				if (secondFastestOnDest) {
					// 计算出最慢的两个
					int srcSlowest = source.get(source.size() - 1);
					int srcSecondSlowest = source.get(source.size() - 2);
					if (destination.get(0) * 2 < srcFastest + srcSecondSlowest) {
						secondFastestOnDest = false;
						totalCrossBridgeTime += populateBridgeCrossingTime(
								source, destination, srcSecondSlowest,
								srcSlowest, true);
					} else {
						totalCrossBridgeTime += populateBridgeCrossingTime(
								source, destination, srcFastest, srcSlowest,
								true);
					}
				} else {
					// 最快的两个人过去
					secondFastestOnDest = true;
					totalCrossBridgeTime += populateBridgeCrossingTime(source,
							destination, srcFastest, srcSecondFastest, true);
				}

			}
		}

		// 输出花费的时间
		System.out.printf("最少过桥耗时 %d 秒！\n", totalCrossBridgeTime);
	}

	/**
	 * 计算过桥的时间，如果需要拿灯回来，则需要将回来的时间也算上。
	 */
	private int populateBridgeCrossingTime(List<Integer> source,
			List<Integer> destination, int fastOne, int slowOne,
			boolean needReturnLight) {
		int sp1 = source.remove(source.indexOf(fastOne));
		int sp2 = source.remove(source.indexOf(slowOne));
		destination.add(sp1);
		destination.add(sp2);
		System.out.printf("%d %d --> Go \n", sp1, sp2);
		// 耗时多的那个
		int elapsedTime = sp2;

		if (needReturnLight) {
			Collections.sort(destination);
			// 拿灯返回
			sp1 = destination.remove(0);
			source.add(sp1);
			Collections.sort(source);
			elapsedTime += sp1;
			// sb.append(sp1).append("\n");
			System.out.printf("%d <-- Back \n", sp1);
		}

		return elapsedTime;
	}

	/**
	 * 保证每个人过桥的时间都大于0
	 */

	private boolean isSpeedParameterLeagal(List<Integer> personSpeeds) {
		/*
		 * 每个人的过桥时间都必须大于0
		 */
		for (int i : personSpeeds) {
			if (i <= 0) {
				return false;
			}
		}
		return true;
	}
}

测试代码

import java.util.Arrays;
import java.util.List;

public class CrossBridgeText {

	public static void main(String[] args) {
		CrossBridge cb = new CrossBridge();
		System.out
				.println("Example 1 -> \n四人夜间过桥，他们只有一个手电筒一次只能两个人过桥，过桥时必须有手电筒，四人过桥时间为1分2分6分10分\n");
		List<Integer> personSpeeds1 = Arrays.asList(1, 2, 6, 10);
		cb.crossBridge(personSpeeds1);
		System.out
				.println("\nExample 2 -> \n小明过桥要一秒，小明的弟弟要三秒，小明的爸爸要六秒，小明的妈妈要八秒，小明的爷爷要十二秒。\n每次此桥最多可过两人，而过桥的速度，依过桥最慢者而定，可是灯在点燃后， 三十秒就会熄灭。\n 那么，请问小明一家，如何在三十秒内过桥？");
		List<Integer> personSpeeds2 = Arrays.asList(1, 3, 6, 8, 12);
		cb.crossBridge(personSpeeds2);
	}

}

测试结果输出：

Example 1 ->
四人夜间过桥，他们只有一个手电筒一次只能两个人过桥，过桥时必须有手电筒，四人过桥时间为1分2分6分10分

1 2 -->
1 <-- Back
6 10 -->
2 <-- Back
1 2 -->
最少过桥耗时 17 秒！

Example 2 ->
小明过桥要一秒，小明的弟弟要三秒，小明的爸爸要六秒，小明的妈妈要八秒，小明的爷爷要十二秒。
每次此桥最多可过两人，而过桥的速度，依过桥最慢者而定，可是灯在点燃后， 三十秒就会熄灭。
那么，请问小明一家，如何在三十秒内过桥？
1 3 -->
1 <-- Back
8 12 -->
3 <-- Back
1 3 -->
1 <-- Back
1 6 -->
最少过桥耗时 29 秒！

转载请注明：http://mouselearnjava.iteye.com/blog/2051541

评论

1 楼 tomakemyself 2014-04-22  

看不懂