1367: 过桥问题

题目描述

有一座桥，每次最多可以过两个人。布罗带着一帮人要过去，总共有n个人，因为是晚上，必须要带手电筒才能过桥。现在问题是手电筒只有一个，如果两个人过桥，需要有一个人拿着手电筒回来带其他人过桥。两个人过桥的时间是由速度慢的人决定的，也就是说如果a需要5的时间过桥，b需要7的时间过桥，那么a和b同时过桥时间为7。

现在布罗想知道，仅靠一个手电筒过桥，最少需要多少时间才能全部人过桥。

输入格式

第一行输入n，第二行输入n个整数，表示每个人过桥的时间（来回的时间是一样的）

输出格式

输出最少需要多少时间

样例输入

4 1 5 2 10

样例输出

17

数据范围

50%数据1<=n<=1000

100%数据1<=n<=500000, 1<=过桥时间<=1000000

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！