算法分析与设计第5版分析题3-3
时间: 2024-06-11 22:09:22 浏览: 15
题目描述:
有n个人要过桥,但是每次只能有两个人一起过,而且只有一个手电筒,过桥的人必须手持手电筒,每个人过桥的时间不同,过桥的时间为t1、t2、t3 … tn,过桥的人每次需两人一起过桥,所以必须有一个人把手电筒送回来给另一个人过桥,问所有人过桥的最短时间。
算法设计:
首先将n个人按照过桥时间从小到大排序,可以利用快排等排序算法。
我们可以用最快的两个人先过桥,假设他们的过桥时间为a和b,那么过桥的时间就是max(a,b)。接下来,最快的人回来,将手电筒交给第二慢的人过桥,过桥时间为b,然后最快的人再回来,将手电筒交给第三慢的人过桥,过桥时间为max(a,b,c)。接下来,最快的人回来,将手电筒交给第四慢的人过桥,过桥时间为b。以此类推,直到最后两个人过桥。
最终的总时间为:t1 + max(t1, t2) + t2 + max(t1, t3, t4) + t3 + max(t1, t5, t6) + t4 + … + max(ti-1, ti) + tn
时间复杂度分析:
排序的时间复杂度为O(nlogn),过桥的时间复杂度为O(n),所以总的时间复杂度为O(nlogn),可以接受。
代码实现:
```python
def bridge(n, times):
times.sort() # 按照过桥时间从小到大排序
total_time = 0
while n > 3:
# 最快的两个人过桥
t1 = times[0]
t2 = times[1]
total_time += t2
# 最快的人回来,将手电筒交给第二慢的人
t3 = times[-1]
total_time += t1
# 第二慢的人过桥
t4 = times[-2]
total_time += t4
# 最快的人回来,将手电筒交给第三慢的人
total_time += t1
# 剩下的人中最快的人过桥
n -= 2
if n == 2:
total_time += t2
else:
t5 = times[1]
t6 = times[-3]
if t5 + t2 < t6 + t4:
total_time += t5 + t2
else:
total_time += t6 + t4
n -= 2
if n == 1: # 剩下一个人过桥
total_time += times[0]
elif n == 2: # 剩下两个人过桥
total_time += times[1]
else: # 剩下三个人过桥
total_time += times[2] + times[0] + times[1]
return total_time
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)