【題目來(lái)源】
http://xiaoye.ac.cn/problem.php?id=2716

【題目描述】
有 n 個(gè)人要渡河，但只有一條小船，這條小船一次只能坐下最多兩個(gè)人，并且只有一副船槳。每個(gè)人劃船的速度不一樣，如果兩個(gè)人一起上船，由于重量變大，劃船的速度相當(dāng)于是劃船速度最慢的那個(gè)人速度。假設(shè)給出每個(gè)人單獨(dú)劃船過(guò)河所花費(fèi)的時(shí)間 Ti，請(qǐng)問(wèn)所有人都過(guò)河的總時(shí)間最短的時(shí)間？

【輸入格式】
輸入兩行，第一行是一個(gè)整數(shù)，表示要過(guò)河的 n 個(gè)人。
第二行，是 n 個(gè)整數(shù)，按速度從快到慢排序好的每個(gè)人劃船過(guò)河的時(shí)間。

【輸出格式】
輸出一行，給出所有人過(guò)河所花費(fèi)最短的時(shí)間。

【輸入樣例】
4
1 2 5 10

【輸出樣例】
17

【算法分析】
● 將各個(gè)過(guò)河時(shí)間從小到大排序并存在數(shù)組 a 中，當(dāng) n≥4 時(shí)，過(guò)河方案為：
方案一：最快的和次快的過(guò)河，然后最快的回來(lái)，再次慢的和最慢的過(guò)河，然后次快的回來(lái)。時(shí)間為 a[1]+2*a[2]+a[n]。
方案二：最快的和最慢的過(guò)河，然后最快的回來(lái)，再最快的和次慢的過(guò)河，然后最快的回來(lái)。時(shí)間為 2*a[1]+a[n-1]+a[n]。
根據(jù)比較結(jié)果，將所選方案的時(shí)間累加到總時(shí)間?s?中，并將人數(shù)?n?減少 2，因?yàn)槊看窝h(huán)處理了兩個(gè)人過(guò)河。

【算法代碼】

#include <bits/stdc++.h>
using namespace std;int main() {int n;cin>>n;int a[n+5];for(int i=1; i<=n; i++) cin>>a[i];sort(a+1,a+n+1);int s=0;while(n>=4) {if(2*a[1]+a[n-1]+a[n]>2*a[2]+a[1]+a[n]) {s+=2*a[2]+a[1]+a[n];} else s+=2*a[1]+a[n-1]+a[n];n-=2;}if(n==3) s+=a[1]+a[2]+a[3];else if(n==2) s+=a[2];else s+=a[1];cout<<s<<endl;return 0;
}/*
in:
4
1 2 5 10out:
17
*/

【參考文獻(xiàn)】
https://blog.csdn.net/u013596478/article/details/105016223
https://mp.weixin.qq.com/s/a9Y2YTpjjmdv2JzI3EtAVw