2013
11-12

# 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))；因为第二种解法如果数组有重复元素 就不正确