过河问题

2024 信息素养智能算法应用 复赛 C++ · 初中组第 4 题、高中组第 1 题（与 2023 高中组同题）

题目描述

有 n 个人要渡河，但只有一条小船，这条小船一次只能坐下最多两个人，并且只有一副船桨。每个人划船的速度不一样，如果两个人一起上船，由于重量变大，划船的速度基本上相当于是划船速度最慢的那个人速度。 （注意船需要有人划回来，并且划回来也需要统计时间。如果所有人都到对岸了，不需要再划回来）

假设给出每个人单独划船过河所花费的时间 Ti，试求所有人都过河的总时间最短的时间？

输入格式

输入两行，第一行是一个整数，表示要过河的 n 个人。

第二行，是 n 个整数，按速度从快到慢排序好的每个人划船过河的时间。

（注：实际数据中每个时间可能各占一行，程序按空白分隔读取即可。）

输出格式

输出一行，给出所有人过河所花费最短的时间。

样例输入 1

（测试数据不包含本样例）

3
1
2
3

样例输出 1

6

样例输入 2

（测试数据不包含本样例）

4
1
2
5
10

样例输出 2

17

针对样例二，一种可行的策略是： A 和 B 先过去：花费 $2$ 分钟。

A 独自划回来：花费 $1$ 分钟。

C 和 D 一起过去：花费 $10$ 分钟。

B 独自划回来：花费 $2$ 分钟。

A 和 B 一起过去：花费 $2$ 分钟。

总时间 = $2 + 1 + 10 + 2 + 2 = 17$。