首页 > 试题广场 >

小强去春游

[编程题]小强去春游

热度指数：2810 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

小强作为强班的班长.决定带着包含他在内的 $n$ 个同学去春游.路程走到一半,发现前面有一条河流.且只有一条小船.经过实验后发现,这个小船一次最多只能运送两个人.而且过河的时间是等于两个人中体重较大的那个人的体重.如果只有一个人,那么过河时间就是这个人的体重.现在小强想请你帮他分析如何安排才能在最短时间内使所有人都通过这条河流.小强很懒,他并不想知道具体怎么过河,只要你告诉他最短的时间.

输入描述:

第一行输入一个整数.表示有组测试数据.
每组数据,第一行输入一个整数.表示人数.
接下来一行输入个整数,表示第个人的体重是.

输出描述:

每组测试数据输出一个答案.

示例1

输入

输出

37
19

算法知识视频讲解

Python

zhq1999

这个题的重点是要找到规律和复杂问题化成子问题？

if __name__ == "__main__":
    n = int(input())
    for i in range(n):
        m = int(input())
        num = list(map(int,input().split()))
        num = sorted(num)
        minTime = 0
        i = m - 1
        while(i >= 3):
            minTime += min(2*num[0]+ num[i] + num[i-1] ,num[i]+2*num[1]+num[0])
            i -= 2
        if i == 2:
            minTime += num[0] + num[1] + num[2]
        elif i == 1:
            minTime += num[1]
        print(minTime)

发表于 2022-08-03 21:24:17 回复(0)