分類討論 ：

訣竅

• 秒數多的一起走,節省時間
• 秒數少的單獨回來接人

兩種 Case :

1. 第一快跟第二快過去，第一快回來，最慢兩個過去，第二快回來。
2. 特殊Case，當第二快也很慢的時候，一快帶最慢過去，第一快回來，第一快帶第二慢過去，第一快回來

第一組人 1, 2, 5, 10 這4個人過橋。方式為 Case 1 ：

• 1秒、2秒的人先過橋，1秒的回來　→　花3秒
• 5秒、10秒的過橋，2秒的回來　→　花12秒
• 最後1秒、2秒的過橋　→　花3秒

第二組人 1, 98, 99, 100 這4個人過橋。方式為 Case 2 ：

• 1秒、98秒的人先過橋，1秒的回來　→　花99秒
• 1秒、99秒的過橋，1秒的回來　→　花100秒
• 最後1秒、100秒的過橋　→　花100秒

第三組人 1, 3, 6, 8, 12 這5個人過橋。方式為 Case 1 ：

• 1秒、3秒的人先過橋，1秒的回來　→　花4秒
• 8秒、12秒的過橋，3秒的回來　→　花15秒
• 1秒、6秒的過橋，1秒的回來　→　花7秒
• 最後1秒、3秒的過橋　→　花3秒

自行完成以下TODO的部分

#include<iostream>
#include <algorithm>
using namespace std;
int N , array[1000001] , sum;

//取最小值
int min( int a , int b ){
    //TODO 什麼時候 return a 什麼時候 return b
}

int main(){

    //N筆資料，代表N個人要過橋
    while ( cin>>N  ){

        int n;

        //輸入n個角色中，每個角色的
        for ( int i = 1 ; i <= N ; i++ )
            cin>>array[i];

        //由小到大排序
        sort ( array + 1 , array + N + 1 );

        sum = 0;

        //未過橋人數>=4人的狀況
        for ( n = N ; n >= 4 ; n -= 2 ){
            //TODO 方案1: 第一快跟第二快過去，第一快回來，最慢兩個過去，第二快回來
            //int t1 = array[1] + array[2] * 2 + array[n];

            //TODO方案2: 第一快帶最慢過去，第一快回來，第一快帶第二慢過去，第一快回來
            //TODO 取時間短的方案 sum += min ( 方案一所花的時間 , 方案二所花的時間 );
        }

        //未過橋人數是3以下的狀況
        if ( n == 3 ){
            //TODO剩下3人時要花費的時間 sum +=......
        }
        else if ( n == 2 ) {
            //TODO剩下2人時要花費的時間
        }
        else if ( n == 1 ){
            //TODO剩下1人時要花費的時間
        }

        cout<<sum<<endl;

    }
    return 0;
}

解答

#include<iostream>
#include <algorithm>
using namespace std;
int N , array[1000001] , sum;

//取最小值
int min( int a , int b ){
    if ( a >= b ) return b;
    else return a;
}

int main(){

    //N筆資料，代表N個人要過橋
    while ( cin>>N  ){

        int n;

        //輸入n個角色中，每個角色的
        for ( int i = 1 ; i <= N ; i++ )
            cin>>array[i];

        //由小到大排序
        sort ( array + 1 , array + N + 1 );

        sum = 0;

        //未過橋人數>=4人的狀況
        for ( n = N ; n >= 4 ; n -= 2 ){
            //方案1: 第一快跟第二快過去，第一快回來，最慢兩個過去，第二快回來
            int t1 = array[1] + array[2] * 2 + array[n];
            //方案2: 第一快帶最慢過去，第一快回來，第一快帶第二慢過去，第一快回來
            int t2 = array[1]*2 + array[n-1] + array[n];
            //取時間短的方案
            sum += min ( t1 , t2 );
        }

        //未過橋人數是3以下的狀況
        if ( n == 3 ) sum += array[3] + array[1] + array[2];
        else if ( n == 2 ) sum += array[2];
        else if ( n == 1 ) sum += array[1];

        cout<<sum<<endl;

    }
    return 0;
}