描述
N个人要过河，但只有一条小船，每次只能坐2人，每个人有不同的划船速度，而两个人一起过河时小船速度由最慢的人的速度决定。请设计一个过河方案，使得所有人均过河，且所用总时间最少。
输入
第一行为正整数N（N<=1000），表示人数，第二行为N个正整数，表示每个人的速度（这里是时间值，值越小速度越快），不超过100。
输出
输出花费最少的总时间。
样例输入
4
1 2 5 10
样例输出
17
先对n个人的速度进行从小到大排序，对于要过河的n个人需要分类讨论
n = 1时，很明显速度就是a[1]
n = 2时，速度是a[2]
n = 3时，最快就是1和n过河，1回来，再和2过去，速度是a[n]+a[1]+a[2]
n = 4时，有两种不同情况，但是两种情况都是要每次送两个人
1. 一直让1号和n号划船，让1号回来；
那么一轮就是 a[n]+a[1]+a[n-1]+a[1]
2.让1号和2号这两个最快和次快过去，然后最快回来，再让最慢的两个n号和n-1号过去，再让次快的2号划船回来；
那么一轮就是 a[2]+a[1]+a[n]+a[2]
然后比较两种情况的最小值相加起来即可，记得要每次n减去2人，这样才能保证n和n-1是最慢和次慢
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e3+10,inf = 0x3f3f3f3f; int a[N]; int n; int main() { cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; sort(a+1,a+1+n); int ans = 0; while(n) { if(n==1) { ans += a[1];break; } else if(n==2) { ans += a[2];break; } else if(n==3) { ans += a[1]+a[2]+a[3];break; } else { ans = ans+min(a[n]+a[1]+a[n-1]+a[1],a[2]+a[1]+a[n]+a[2]); n-=2; } } cout<<ans; return 0; }