玄关 求助贪心题目

题目描述 有n个人要过河，只有一艘最多载两个人的船，第i个人独自划船过河的时间为$a_i$。若有两个人一同过 河，则花费时间为，两个人的过河时间较长者。 求至少需要多少时间，才能让n个人从一侧都移动到另一侧。 输入格式 输入的第一行包含唯一一个整数 n，描述了需要过河的人数。 接下来的 n行中第 i行包含一个整数$a_i$，意义见上。 输出格式 输出一个整数，表示答案。

数据范围 2<=n<=100,1<=$a_i$<=600

样例 :

样例输入 4 1 10 5 2

样例输出 17

对于第一个样例：

先让第 1个人与第 4个人过河，耗费时间为max{1,2}=2。

接着让第 1个人独自从对岸划回来，耗费时间为 1。

接着让第 2,3个人一同过河，耗费时间为10 。

接着让第 4个人独自从对岸划回来，耗费时间为 2。

最后第 1个人与第 个人过河，耗费时间为 2。 总的时间为 2+1+10+2+2=17，容易证明不存在更优秀的方案。