最快的过河时间 - 小船过河问题算法详解及Python实现
最快的过河时间 - 小船过河问题算法详解及Python实现
**题目：** N个人过河，船每次只能坐两个人，船载每个人过河的所需时间不同t[i]，每次过河的时间为船上的人的较慢的那个，求最快的过河时间。(船划过去要有一个人划回来)
**解题思路：**
1. 首先将所有人按照过河所需时间从小到大排序。
2. 假设最快的两个人为A和B，最慢的两个人为Y和Z。
3. 有两种情况：
a. A和B先过河，A回来，然后Y和Z过河，B回来，最后A和B再过河。此时总时间为t[B] + t[A] + t[Z] + t[A]。
b. A和Z先过河，A回来，然后A和Y过河，A回来，最后A和B再过河。此时总时间为t[Z] + t[A] + t[Y] + t[A]。
4. 比较两种情况的总时间，取最小值即为最快的过河时间。
**代码实现：**
```python
def fastest_time(t):
n = len(t) # 总人数
t.sort() # 按过河所需时间排序
if n <= 2: # 如果人数小于等于2，则直接返回最大的时间
return t[-1]
time1 = t[1] + t[0] + t[n-1] + t[1] # A和B先过河，A回来，然后Y和Z过河，B回来，最后A和B再过河
time2 = t[n-1] + t[0] + t[n-2] + t[0] # A和Z先过河，A回来，然后A和Y过河，A回来，最后A和B再过河
return min(time1, time2)
# 测试样例
t = [3, 1, 6, 2, 8]
print(fastest_time(t)) # 输出：19
```
原文地址: https://www.cveoy.top/t/topic/pKVl 著作权归作者所有。请勿转载和采集!