2023年华为OD机考真题：士兵过河II

全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。

真题库：https://www.yuque.com/codernav.com/od

题目：士兵过河II
知识点二分查找排序
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
一支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）两个士兵的同时划船时，如果划速不同则会导致船原地转圈圈；所以为保持两个士兵划速相同，则需要向划的慢的士兵看齐。
2）两个士兵坐船时，重量增加吃水加深，水的阻力增大；同样的力量划船速度会变慢；
3）由于河水湍急大量的力用来抵消水流的阻力，所2）中过河用时不是a[i] * 2，而是a[i] * 10
示例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
解题思路：
这道题没有找到满分答案，平均分10分。博主根据例题写了一下，大家多提提问题，看看该怎样改进一下！
如例二：
5
130
50 12 13 15 20
1、先对士兵进行排序：12 13 15 20 50
2、左边士兵先过河：12 13
12<13且13<12*10，所以耗时为13；对岸士兵12 13，让速度快（12）的返程；岸边士兵 12 15 20 50，对岸士兵13；总耗时13+12=25<130，符合要求
3、右边士兵开始过河：20 50
20<50 且 50<20*10，所以耗时为50；对岸士兵13 20 50，让速度快（13）返程；岸边士兵12 13 15，对岸士兵20 50；25+50+13=88<130，符合要求
4、左边士兵开始过河：12 13
12<13且13<12*10，所以耗时为13；对岸士兵12 13 20 50，让速度快（12）的返程；岸边士兵 12 15，对岸士兵13 20 50；总耗时88+13+12=113<130，符合要求
5、右侧士兵开始过河：12 15
12<15 且 15<12*10，所以耗时为15；对岸士兵12 13 15 20 50，岸边没有士兵，过河结束，总耗时：113+15=128<130，符合要求

代码实现：

package com.codernav.demo.hwod.exam;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

/**
 * @title 士兵过河II
 * @Description 一支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）如果士兵下河游泳，则会被湍急水流直接带走，算作死亡。
 * 请帮忙给出一种解决方案，保证存活的士兵最多，且过河用时最短。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/28
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int T = sc.nextInt();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            list.add(sc.nextInt());
        }
        boolean isLeft = true;      //是否从左侧士兵开始过河
        boolean isRight = true;     //右侧士兵是否满足过河条件（排序后右侧士兵耗时长）
        int time = 0;       //过河时间
        int count = 0;      //过河士兵数量
        int returnTime = 0;     //最后一人的返程时间
        List<Integer> duian = new ArrayList<>();    //对岸的士兵集合

        while (list.size() != 0) {
            Collections.sort(list);     //对士兵进行排序
            int a, b;       //坐船的两个士兵
            if (isLeft) {     //左侧士兵开始过河或者右侧士兵无法过河
                a = list.get(0);    //左侧第一个士兵
                b = list.get(1);    //左侧第二个士兵
                list.remove(0);     //过河的士兵需要移除
                list.remove(0);
            } else {
                a = list.get(list.size() - 2);    //右侧第一个士兵（倒数第二个士兵）
                b = list.get(list.size() - 1);    //右侧第二个士兵（倒数第一个士兵）
                list.remove(list.size() - 1);
                list.remove(list.size() - 1);
            }

            count += 2;
            int tempTime;   //当前两个士兵的过河最优时间
            if (a > b) {
                tempTime = Math.min(a, b * 10);    //找出两人划船的最优方案
            } else {
                tempTime = Math.min(b, a * 10);
            }

            if (time + tempTime >= T) {       //此时时间已经超时
                if (isLeft) {     //如果是左侧的士兵则表示时间已经不够了（因为右侧士兵的耗时更长）
                    if (time + tempTime == T) {   //时间刚刚好
                        time += tempTime;
                    } else {
                        count--;   //时间超了需要将此次过河的人剔除
                        time -= returnTime;     //上一次返程时间也取消了
                    }
                    break;  //跳出循环，表示之后不能有士兵过河了
                } else {
                    count -= 2;     //过河人数还原
                    isRight = false;    //右侧不再满足过河的时间
                    isLeft = true;
                    list.add(a);    //过河士兵返回岸边
                    list.add(b);
                }
            } else {
                time += tempTime;   //到此刻士兵过河所花的时间和
                if (list.size() == 0) {   //士兵已经全部过河直接跳出循环
                    break;
                }

                duian.add(a);   //对岸的士兵集合添加两个已经过河的士兵
                duian.add(b);

                Collections.sort(duian);    //求出对岸滑的最快的士兵，让他返程
                returnTime = duian.get(0);
                time += returnTime;   //最快的士兵返程所花时间也要加上

                if (time >= T) {  //此时时间已经超时
                    time -= duian.get(0);   //减去返程所花的时间
                    if (isLeft) {
                        break;  //如果是左侧士兵则表示之后没有士兵能够过河
                    } else {
                        time -= tempTime;   //右侧士兵则恢复原样，让左侧的士兵再试试
                        isRight = false;    //右侧士兵不能再过河了
                        isLeft = true;
                        count -= 2;     //过河人数还原
                        duian.remove(duian.size() - 1);   //对岸的士兵返回岸边
                        duian.remove(duian.size() - 1);
                        list.add(a);
                        list.add(b);
                    }
                } else {
                    list.add(duian.get(0));     //岸边添加返程的士兵
                    duian.remove(0);    //对岸移除返程的士兵
                    isLeft = !isRight || !isLeft;      //如果右侧士兵无法过河则永远从左侧士兵中选
                    count--;       //过河人数减一（因为返程了）
                }
            }
        }
        System.out.println(count + " " + time);
    }
}