过桥 ## 来源 ZOJ Monthly, April 2003 (ZOJ1579) ## 题目描述 有一家人，共N人，要在晚上过一座桥。由于天非常黑，他们提着一盏灯过桥。不幸的是，桥很窄，因此同一时刻最多允许两人同时过桥，而且过桥时必须提着灯。每个人过桥的速度不一样，而且两个人同时过桥时只能以两者的速度中较小的速度过桥。问题是，给定家庭的人数N，以及每个人单独过桥所需的时间，求整个家庭全部通过桥所需的最少时间。 ## 输入描述 输入文件中包含多个测试数据。每个测试数据占2行：第1行位一个整数N，满足0≤N≤100000；第2行，给定了N个整数，为每个人单独过桥时所需的时间。 ## 输出描述 对每个测试数据，输出一行，为整个家庭全部通过桥所需的最少时间。 ## 样例输入 ```txt 5 1 3 6 8 12 3 7 8 9 ``` ## 样例输出 ```txt 29 24 ```