首页 > 专题系列 > Java解POJ > POJ 3404 Bridge over a rough river [解题报告] Java
2013
11-12

POJ 3404 Bridge over a rough river [解题报告] Java

Bridge over a rough river

问题描述 :

A group of N travelers (1 ≤ N ≤ 50) has approached an old and shabby bridge and wishes to cross the river as soon as possible. However, there can be no more than two persons on the bridge at a time. Besides it’s necessary to light the way with a torch for safe crossing but the group has only one torch.

Each traveler needs ti seconds to cross the river on the bridge; i=1, … , N (ti are integers from 1 to 100). If two travelers are crossing together their crossing time is the time of the slowest traveler.

The task is to determine minimal crossing time for the whole group.

输入:

The input consists of two lines: the first line contains the value of N and the second one contains the values of ti (separated by one or several spaces).

输出:

The output contains one line with the result.

样例输入:

4
6 7 6 5

样例输出:

29

解题代码:

//* @author: ccQ.SuperSupper
import java.util.*;
import java.math.*;

public class Main {
	
 public static void main(String[] args) {
		
	int i,n,ans;
	int way[] = new int[60];
	Scanner cin = new Scanner(System.in);
	
	while(cin.hasNext())
	{
		n = cin.nextInt();
		for(i=0;i< n;++i)
			way[i] = cin.nextInt();
		Arrays.sort(way,0,n);
		ans = search(n,way);
		System.out.println(ans);
	}
   }

  public static int search(int n,int way[])
  {
	int  ans=0,i,j;
	if(n==1) return way[0];
	if(n==2) return way[1];
	if(n==3) return min(way[2]+way[0]+way[1],way[2]+way[1]+way[1]);
	return search(n-2,way)+min(way[n-1]+way[0]+way[1]+way[1],way[n-1]+way[n-2]+way[0]+way[0]);
   }
	public static int min(int a,int b)
	{
		if(a>b) return b;
		return a;
	}
	
}

  1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确