Skip to content

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了,可以的话,请您参考添加页面,与大家一起分享你的题解!