两人过河

有 n 个人希望在晚上通过一座桥。

在任何时刻，最多只能有两个人在桥上，并且必须要带着手电筒才能过桥。

现在只有一个手电筒，所以必须安排某种顺序，使得手电筒可以被带回去让更多的人过桥。

每个人都有不同的过桥时间，两个人一起过桥所用的时间等于其中较慢的一个人的过桥时间。

现求所有人过桥的最短时间。

输入

第一行一个整数 n。（1 ≤ n ≤ 1000）

接下来 n 行，每行一个整数表示第 i 人的过桥时间 Ti。（1 ≤ Ti ≤ 100）

输出

输出所有人过桥的最短时间。

样例：

1
2
3
4
5
4
1
5
2
10
1
17

让 1, 2 先过桥，然后让 1 回来，让 5,10 过桥，然后 2 回来再和 1 一起过桥，时间为 2+1+10+2+2=17。

思路

==思路==：让时间短的人优先过桥，作为工具人。

  1. 递归解决问题
  2. 有时使用1个人当工具人过桥时间较短，有时使用2个人当工具人过桥时间较短
  3. 取两种方案中速度较快的一种（将两种方案结合起来）

参考代码

设最快的过桥时间为num[0]、次快过桥时间为num[1]、次慢过桥时间为num[i - 1]、最慢过桥时间为num[i]：

则有：

  • n = 1时，最快过桥时间为num[0]
  • n = 2时，最快过桥时间为num[1]
  • n = 3时，最快过桥时间为num[1] + num[0] + num[2]
  • n > 3时，最快过桥时间为
    • 方案1（2个工具人）：num[1] + num[0] + num[i] + num[1]（此时两个工具人都在起点）
    • 方案2（1个工具人）：num[i] + num[0] + num[i - 1] + num[0]（此时工具人在起点）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<algorithm>
using namespace std;

int n, num[1005];
int ans;

int main() {
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> num[i];
	sort(num, num + n);
	//从最慢的人开始遍历 每次过桥两个人
	for (int i = n - 1; 1; i -= 2) {
		if (i == 0) {//只剩1个人需要过桥
			ans += num[0];
			break;
		} else if (i == 1) {//只剩2个人需要过桥
			ans += num[1];
			break;
		} else if (i == 2) {//只剩3个人需要过桥
			ans += num[1] + num[0] + num[2];
			break;
		} else {//剩余4个及以上则每次过两个人 取两种方案的最小值
			ans += min(num[1] + num[0] + num[i] + num[1], num[i] + num[0] + num[i - 1] + num[0]);
		}
	}
	cout << ans << endl;
	return 0;
}