A33759. 编程实现:（P1809 过河问题）小青要赶 N (2<N<100) 匹小马过河，N 匹小马过河都需要一定的时间(分钟)，小青每次过河最多能赶两匹小马 (骑一并赶一匹)，返回时需骑一匹，每次过河的时间为走的慢的小马花费的时间。请计算至少需要多长时间才能把 N 匹小马全部赶过河。例如: N = 4，4 匹小马过河需要的时间分别为 1，2，3，4 (单位: 分钟)。用时最少的一种过河方式:第一次:赶 …
填空题
困难
知识点
题目描述
编程实现:（P1809 过河问题）
小青要赶 N (2<N<100) 匹小马过河，N 匹小马过河都需要一定的时间(分钟)，小青每次过河最多能赶两匹小马 (骑一并赶一匹)，返回时需骑一匹，每次过河的时间为走的慢的小马花费的时间。请计算至少需要多长时间才能把 N 匹小马全部赶过河。
例如: N = 4，4 匹小马过河需要的时间分别为 1，2，3，4 (单位: 分钟)。
用时最少的一种过河方式:
第一次:赶 1 分钟和 2 分钟的小马过河，然后骑 1 分钟的小马返回，共花费 3 分钟 (过去花费 2 分钟，回来花费 1 分钟)
第二次:赶 3 分钟和 4 分钟的小马过河，然后骑 2 分钟的小马返回，共花费 6 分钟 (过去花费 4 分钟，回来花费 2 分钟)
第三次: 赶 1 分钟和 2 分钟的小马过河，共花费 2 分钟 (过去花费 2 分钟)
总共最少花费的时间是 11 分钟（3+6+2=11）
输入说明
两行整数，第一行表示总共有多少匹马 N（2<N<100），第二行表示每匹马过河所需要的时间，数字之间以英文逗号隔开
输出说明
一行一个整数，表示将所有马儿赶过河所需要的最短时间
输入样例
4
1,2,3,4
输出样例
11
参考答案
m = int(input())
a = list(map(int,input().split(',')))
ans = 0
a.sort()
while m>=4:
ans += min(a[0]+a[1]*2+a[m-1], a[0]*2+a[m-2]+a[m-1])
m -=2
if m ==3:
ans +=a[0]+a[1]+a[2]
if m==2:
ans += a[1]
if m==1:
ans += a[0]
print(ans)
上一题
下一题