題敘：https://zerojudge.tw/ShowProblem?problemid=d872
解題想法：
- 先把 n 個人過橋需要的時間，由小到大排序 (A <= B <= C <= … <= X <= Y <= Z)。
- Base conditions:
- n == 0：花費時間 0
- n == 1：花費時間 A
- n == 2：花費時間 B
- n == 3：(AC)一起過橋 -> A帶回手電筒 -> (AB)一起過橋：花費時間 C+A+B。
- 當人數n >= 4, 有兩種策略(選擇(1)(2)兩個方案中時間較短的)：
- 1. (AB)一起過橋 -> A帶回手電筒 -> (YZ)一起過橋 -> B帶回手電筒：花費時間 B+A+Z+B。
- 2. (AZ)一起過橋 -> A帶回手電筒 -> (AY)一起過橋-> A帶回手電筒：花費時間 Z+A+Y+A。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, a, x, y;
long long ans;
vector <int> v;
while (cin >> n){
if (n == 0){
cout << 0 << "\n";
continue;
}
v.clear();
ans = 0;
for (int i = 0; i < n; i++){
cin >> a;
v.push_back(a);
}
sort(v.begin(), v.end());
while (v.size() >= 4){
x = v[0] * 2 + v[v.size()-2] + v[v.size()-1];
y = v[0] + v[1] * 2 + v[v.size()-1];
ans += min(x, y);
v.resize(v.size()-2);
}
if (v.size() == 3){
for (int i:v){
ans += i;
}
}else if (v.size() == 2){
ans += v[1];
}else{
ans += v[0];
}
cout << ans << "\n";
}
}