链接：https://ac.nowcoder.com/acm/contest/5968/C

题目描述

牛市的幸存的先民在流星雨之后就忍痛离开了这片土地，选择迁徙，在迁徙的途中，他们需要渡过一条河。因为牛市的树木在流星雨中被严重破坏，所以他们只造出了一艘小船，船太小了，一次只能乘坐两人。
牛市的先民们每个人划船的速度都不尽相同，所以每个人都有一个渡河时间T，为了保证船的平衡，当穿上有两个人的时候，需要他们按照慢的那个人的速度划船，也就是说船到达对岸的时间等于船上渡河时间长的那个人的时间。
现在已知N个人的渡河时间T，请问最少要花费多少时间，才能使所有人都过河。

输入描述:

输入文件第一行为先民的人数N(N\leq 100000)(N≤100000)，以下有N行，每行一个整数为每个人的渡河时间。

输出描述:

输出文件仅包含一个数，表示所有人都渡过河的最少渡河时间。
示例1
输入
4
5
7
11
16
输出
42
说明
首先1，2先到河对岸花费7，然后1回来花费5，3，4到河对岸花费16，2回来花费7，1，2再到河对岸花费7

#include<iostream>
#include<algorithm>
using namespace std;
int n;
int t[100005],dp[100005];
int main() {
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>t[i];
    sort(t+1,t+n+1);
    dp[1]=t[1];//如果只有一个人，那么用时就是他的时间 
    dp[2]=t[2];//如果两个人，那么用时就是排序后用时长的人的时间 
    for(int i=3; i<=n; i++){
        dp[i]=min(dp[i-1]+t[1]+t[i],dp[i-2]+t[1]+2*t[2]+t[i]);
    }//如果人数>=3 
    //1.渡河了的回去一个用时最少的接人
    //2.渡河了的回去两个用时最少的接人，两个用时多的一起过河，两个用时少的一起过河 
    //例如还有两个人未渡河，他们用时为20，21，已经渡河的人中用时最少的两个为5，6
    //那么5，6同时 回去接人，比5回去接两次人用时少
    //所以我们只需要取这两种情况用时少的即可 
    cout<<dp[n];
    return 0;
}