首页 > 专题系列 > Java解POJ > POJ 1700 Crossing River [解题报告] Java
2013
11-10

POJ 1700 Crossing River [解题报告] Java

Crossing River

问题描述 :

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.

输入:

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.

输出:

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

样例输入:

1
4
1 2 5 10

样例输出:

17

解题代码:

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

public class Main {

	private static int sum;

	public static int getSumTime(int[] a, int n) {
		
		if (n < 3) {
			 return a[n-1];
		} else if (n == 3) {
			return a[0] + a[1] + a[2];
		} else {
			int temp1 = a[n-1] + a[0] + a[n - 2] + a[0];
			int temp2 = a[1] + a[0] + a[n-1] + a[1];
			
			if (temp1 < temp2){
				return  temp1 + getSumTime(a, n - 2);
			}
			else if (temp2 < temp1){
				return  temp2 + getSumTime(a, n - 2); 
			}else{
				return  temp2 + getSumTime(a, n - 2); 
			}
		}
	}

	public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);
          int t = sc.nextInt();
          for(int i = 0; i < t ; i++){
        	  int n = sc.nextInt();
        	  int[] a = new int[n];
        	  for(int j = 0; j < n ; j++){
        		  a[j] = sc.nextInt();
        	  }
        	  Arrays.sort(a);
        	  System.out.println(Main.getSumTime(a, n));
          }     
	}

}

  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮