思路
每次将速度最慢的两个人$C、D(C < D)$过桥。
策略1:最快的人$A$带$C$过桥,$A$再送回手电筒,再带$D$过桥,$A$再送回手电。总时间$T1=A+C+D+A$;策略2:最快的两人$A、B$先过桥,$A$送回手电,$C、D$一同过桥,$B$再送回手电,$T2=B+A+D+B$,选择耗时较小的策略即可。
C++代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int t[N];
int dfs(int n)
{
if(n == 1) return t[1];
if(n == 2) return t[2];
if(n == 3) return t[1] + t[2] + t[3];
if(t[n] + t[n - 1] + t[1] + t[1] < t[2] + t[1] + t[n] + t[2])
return dfs(n - 2) + t[n] + t[n - 1] + t[1] * 2;
return dfs(n - 2) + t[1] + t[2] + t[2] + t[n];
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", &t[i]);
sort(t + 1, t + n + 1);
cout << dfs(n) << endl;
return 0;
}