Bridge over a rough river

POJ - 3404 Bridge over a rough river

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 4427		Accepted: 1824

Description

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 t_i seconds to cross the river on the bridge; i=1, ... , N (t_i 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.

Input

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

Output

The output contains one line with the result.

Sample Input

4
6 7 6 5

Sample Output

29

Source

Northeastern Europe 2001, Western Subregion OJ-ID：
poj-3404

author：
Caution_X

date of submission：
20191010

tags：
Ad Hoc

description modelling：
n个人过桥，每个人过桥用时已给出，桥只能承载两个人，过河需要火炬，但是只有一个火炬，问最短过河时间

major steps to solve it：
1.两个人过桥之后需要有人把火炬送回来
2.以未过桥的四个人为一个单位，记为a,b,c,d其中a最快，b次快，c最慢，d次慢，分两种情况，①：每次都由最快的人把火炬送回来②：由最快帮助最慢过河，次快帮助次慢过河,步骤为a,b先过河，然后a回来，c,d一起过河，然后b回来带a过河
两种方式耗时为：①：2a+c+d ②：2b+a+c
3.每次以四人为单位选择过河方式直到剩下的人不足四人为止
warnings：
1.思维误区：容易认为方案一是唯一最有效方案

AC Code:

#include<cstdio>
#include<algorithm>
using namespace std;
int a[55];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
    }
    if(n==1)    printf("%d\n",a[1]);
    else { 
        int ans=0;
        sort(a+1,a+n+1);
        while(n>3) {
            if(a[1]+a[n-1]<2*a[2]) {
                ans+=a[n]+a[1]*2+a[n-1];
            }
            else {
                ans+=a[2]+a[1]+a[2]+a[n];
            }    
            n-=2;
        }
        if(n==2) ans+=a[2];
        else ans+=a[1]+a[2]+a[3];
        printf("%d\n",ans);    
    } 
    return 0;
}