算法（蓝桥杯）贪心算法7——过河的最短时间问题解析
一、题目描述
在漆黑的夜里，N位旅行者来到了一座狭窄且没有护栏的桥边。他们只带了一只手电筒，且桥窄得只够让两个人同时过。如果各自单独过桥，N人所需的时间已知；若两人同时过桥，则所需时间是走得较慢的那个人单独行动时所需的时间。任务是设计一个方案，让这N人尽快过桥，并计算出这N个人的最短过桥时间。
二、解答思路
要解决这个问题，关键在于合理安排过桥顺序，使总时间最短。以下是两种常见的策略：
（一）最快两人先过桥策略
步骤：
让速度最快的两个人先过桥。
然后让速度最快的人回来，再带剩下的人过桥。
重复上述过程，直到所有人都过桥。
示例：
假设有四个人甲乙丙丁，过河时间分别为甲：1，乙：2，丙：5，丁：10。
先让甲乙过去（2分钟），甲回来（1分钟），甲丙过去（5分钟），甲回来（1分钟），甲丁再过去（10分钟），总共需要19分钟。
（二）最慢两人一起过桥策略
步骤：
先让速度最快的两个人过桥。
然后让速度最快的人回来，接着让速度最慢的两个人一起过桥。
速度第二快的人回来，再让速度最快的两个人过桥。
重复上述过程，直到所有人都过桥。
示例：
同样是甲乙丙丁四个人，先让甲乙过去（2分钟），甲回来（1分钟），丙丁过去（10分钟），乙回来（2分钟），甲乙再过去（2分钟），总共需要17分钟。
三、代码分析
本题最优策略为策略二，对策略二进行分析，以下是针对该问题的Python代码实现及其分析：
Python复制
n=int(input()) a=[int(i) for i in input().split()] a=sorted(a) b=n//2 if n%2==0: sum =0 for i in range(n): if i==0: sum=sum+(b-1)*a[i] elif i==1: sum=sum+(n-1)*a[i] elif i%2!=0: sum=sum+a[i] else: sum=a[0] for i in range(n): if i==0: sum=sum+(b-1)*a[i] elif i==1: sum=sum+(n-2)*a[i] elif i%2==0: sum+=a[i] if len(a)==1: print(a[0]) else: print(sum)（一）代码逻辑
输入处理：
首先通过
input()函数读取输入的整数N，表示过河的人数。然后读取N个整数，表示每个人过河所需的时间，并将这些时间存储在列表
a中。排序：
使用
sorted(a)对列表a进行排序，这样可以方便后续根据速度安排过河顺序。计算最短时间：
计算
n//2的值，存储在变量b中，用于后续计算。通过
if n%2==0判断人数N是否为偶数，从而选择不同的计算策略。在循环中，根据不同条件累加过河时间：
当
i==0时，表示速度最快的人，其过河次数与b-1有关。当
i==1时，表示速度第二快的人，其过河次数与n-1或n-2有关，具体取决于人数的奇偶性。对于其他情况，根据
i%2的值判断是奇数还是偶数索引，分别累加对应的时间。最后，如果人数为1，直接输出该人的过河时间；否则输出计算得到的总时间
sum。（二）代码优化建议
变量命名：
变量
b的命名不够直观，建议改为更具描述性的名字，如half_n，表示人数的一半。逻辑简化：
代码中存在重复的逻辑，如
if i==0和elif i==1的部分在两种情况下都有出现，可以考虑提取公共部分，减少代码冗余。注释添加：
在关键代码段添加注释，解释每个步骤的作用和计算逻辑，便于他人理解和维护代码。
四、总结
过河的最短时间问题是一个典型的优化问题，通过合理安排过桥顺序，可以有效减少总时间。在解决此类问题时，需要仔细分析不同策略的优劣，并通过编程实现最优解。希望本文的解答和代码分析能帮助你更好地理解和解决这个问题。
原文地址：https://blog.csdn.net/m0_73581472/article/details/145216607
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！