【华为OD机试真题】A卷-士兵过河（Python）

一、题目描述

【华为OD机试真题】A卷-士兵过河（Python）

题目描述：

一支N个士兵的军队正在趁夜色逃亡，途中遇到一条湍急的大河。 敌军在T的时长后到达河面，没到过对岸的士兵都会被消灭。 现在军队只找到了1只小船，这船最多能同时坐上2个士兵。
1）当1个士兵划船过河，用时为 a[i]；0 <= i < N

2）当2个士兵坐船同时划船过河时，用时为max(a[j],a[i])两士兵中用时最长的。

3）当2个士兵坐船1个士兵划船时，用时为 a[i]*10；a[i]为划船士兵用时。

4）如果士兵下河游泳，则会被湍急水流直接带走，算作死亡。 请帮忙给出一种解决方案，保证存活的士兵最多，且过河用时最短。

二、输入输出

输入描述：
第一行：N 表示士兵数(0<N<1,000,000) 
第二行：T 表示敌军到达时长(0 < T < 100,000,000) 
第三行：a[0] a[1] … a[i]… a[N- 1] 
a[i]表示每个士兵的过河时长。 
(10 < a[i]< 100; 0<= i< N）
输出描述：
第一行：”最多存活士兵数” “最短用时”

三、参考示例

示例1 输入输出示例仅供调试，后台判题数据一般不包含示例
输入：
5
43
12 13 15 20 50
输出：
3 40
说明：
可以达到或小于43的一种方案： 
第一步：a[0] a[1] 过河用时：13 
第二步：a[0] 返回用时：12 
第三步：a[0] a[2] 过河用时：15
示例2 输入输出示例仅供调试，后台判题数据一般不包含示例
输入：
5
130
50 12 13 15 20
输出：
5 128
说明：
可以达到或小于130的一种方案： 
第一步：a[1] a[2] 过河用时：13 
第二步：a[1] 返回用时：12 
第三步：a[0] a[5] 过河用时：50 
第四步：a[2] 返回用时：13 
第五步：a[1] a[2] 过河用时：13 
第六步：a[1] 返回用时：12 
第七步：a[1] a[3] 过河用时：15 
所以输出为：5 128
示例3 输入输出示例仅供调试，后台判题数据一般不包含示例
输入：
7
171
25 12 13 15 20 35 20
输出：
7 171
说明
可以达到或小于60的一种方案： 
第一步：a[1] a[2] 过桥用时：13 
第二步：a[1] 带火把返回用时：12 
第三步：a[0] a[5] 过桥用时：35 
第四步：a[2] 带火把返回用时：13 
第五步：a[1] a[2] 过桥用时：13 
第六步：a[1] 带火把返回用时：12 
第七步：a[4] a[6] 过桥用时：20 
第八步：a[2] 带火把返回用时：13 
第九步：a[1] a[3] 过桥用时：15 
第十步：a[1] 带火把返回用时：12 
第十一步：a[1] a[2] 过桥用时：13
所以输出为：
7 171
备注：
1）两个士兵的同时划船时，如果划速不同则会导致船原地转圈圈；所以为保持两个士兵划速相同，则需要向划的慢的士兵看齐。 2）两个士兵坐船时，重量增加吃水加深，水的阻力增大；同样的力量划船速度会变慢； 3）由于河水湍急大量的力用来抵消水流的阻力，所以2）中过河用时不是a[i] *2， 而是a[i] * 10。

四、解题思路

1. 定义一个 TreeNode 类来表示树节点。
2. 定义一个函数 shorter_time 来返回两个数中较小的值。
3. 处理输入，读取 N 和 T 的值，以及列表 a。
4. 对列表 a 进行排序。
5. 初始化一个长度为 N 的列表 dp，用于存储中间结果。
6. 使用动态规划的思想，计算 dp 数组的值。
7. 如果计算过程中超过了阈值 T，则输出结果并结束计算。

五、参考代码 

# -*- coding: utf-8 -*-
'''
@Time    :   2023/12/10 00:09:00
@Author  :   mgc 
@Version :   1.0
@Desc    :   None
'''

# import os
# import re
# import sys
# import copy
# import math
# import queue
# import functools
# from queue import Queue
# from collections import Counter, defaultdict

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def shorter_time(a, b):
    # 返回较小的值
    if a * 10 < b:
        return a * 10
    return b

# 处理输入
N = int(input())
T = int(input())
a = [int(x) for x in input().split(" ")]
a = sorted(a)

dp = [0 for _ in range(N)]

skip_flag = False
for i in range(N):
    if i == 0:
        dp[0] = a[0]
        if dp[0] > T:
            print("0 0")
            skip_flag = True
            break
    elif i == 1:
        dp[1] = a[1]
    else:
        dp[i] = min(dp[i - 1] + a[i] + a[0], dp[i - 2] + a[0] + a[i] + a[1] + a[1])

    if dp[i] > T:
        skip_flag = True
        print(str(i) + " " + str(dp[i - 1]))
        break

if not skip_flag:
    print(str(N) + " " + str(dp[N - 1]))

六、华为OD机试真题汇总目录

    【华为OD机试】真题汇总A+B+C+D券（Python实现）

    【华为OD机试】真题汇总A+B+C+D卷（JAVA实现）

    【华为OD机试】真题汇总A+B+C+D卷（C++实现）