Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

Crossing River

Posted on Edited on In , ,
Symbols count in article: 1.9k Reading time ≈ 2 mins.

来源POJ第1700题Crossing River

Description

A group of N people wishes to go across a river with only one boat, which can at most carry two persons. Therefore some sort of shuttle arrangement must be arranged in order to row the boat back and forth so that all people may cross. Each person has a different rowing speed; the speed of a couple is determined by the speed of the slower one. Your job is to determine a strategy that minimizes the time for these people to get across.

Input

The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases. Then T cases follow. The first line of each case contains N, and the second line contains N integers giving the time for each people to cross the river. Each case is preceded by a blank line. There won’t be more than 1000 people and nobody takes more than 100 seconds to cross.

Output

For each test case, print a line containing the total number of seconds required for all the N people to cross the river.

Sample Input

1
2
3
1
4
1 2 5 10

Sample Output

1
17

思路比较简单，分情况讨论，1个人过河，时长取最短的，2个人，时长取nums[1]，3个人取nums[0] + nums[1] + nums[2],当人数增加到4个人以上时要讨论，最快的(即所用时间nums[0])和次快的过河,然后最快的将船划回来,再次慢的和最慢的过河,然后次快的将船划回来.即所需时间为:nums[0]+2nums[1]+nums[n-1],最快的和最慢的过河,然后最快的将船划回来,再最快的和次慢的过河,然后最快的将船划回来.即所需时间为:2nums[0]+nums[n-2]+nums[n-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
30
31
32
33
34
35
36
37
38
39
40
import java.util.*;

public class Main {

	//public static int[] nums;
	//public static long mid;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int all = in.nextInt(), len, ans = 0;
		while (all > 0) {
			ans = 0;
			len = in.nextInt();
			int[] nums = new int[len];
			for (int i = 0; i < len; i++)
				nums[i] = in.nextInt();
			Arrays.sort(nums);
			int times = len;
			while(times > 0) {
				if (times == 1) {  //特殊情况1
					ans += nums[0];
					break;
				} else if (times == 2) {  //特殊情况2
					ans += nums[1];
					break;
				} else if (times == 3) {  //特殊情况3
					//0 2 过河，0回来，0 1 过河
					ans += nums[0] + nums[1] + nums[2];
					break;
				} else {
					ans += Math.min(2 * nums[1] + nums[0] + nums[times - 1], nums[times - 1] + 2 * nums[0] + nums[times - 2]);
					times -= 2;
				}
			}
			System.out.println(ans);
			all--;
		}

	}
}