华为OD机试 - 猴子吃桃 - 二分查找（Java 2024 C卷 100分）

news/2024/7/20 19:34:47 标签: 华为od, java, 二分查找, 猴子吃桃

在这里插入图片描述

华为OD机试 2024C卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

孙悟空喜欢吃蟠桃，一天他乘守卫蟠桃园的天兵天将离开了而偷偷的来到王母娘娘的蟠桃园偷吃蟠桃。

已知蟠桃园有 N 棵蟠桃树，第 i 棵蟠桃树上有 N[i]（大于 0）个蟠桃，天兵天将将在 H（不小于蟠桃树棵数）小时后回来。

孙悟空可以决定他吃蟠桃的速度 K（单位：个/小时），每个小时他会选择一颗蟠桃树，从中吃掉 K 个蟠桃，如果这棵树上的蟠桃数小于 K，他将吃掉这棵树上所有蟠桃，然后这一小时内不再吃其余蟠桃树上的蟠桃。

孙悟空喜欢慢慢吃，但仍想在天兵天将回来前将所有蟠桃吃完。

求孙悟空可以在 H 小时内吃掉所有蟠桃的最小速度 K（K 为整数）。

二、输入描述

从标准输入中读取一行数字，前面数字表示每棵数上蟠桃个数，最后的数字表示天兵天将将离开的时间。

三、输出描述

吃掉所有蟠桃的 最小速度 K（K 为整数）或 输入异常时输出 -1。

1、输入

3 11 6 7 8

2、输出

4

3、说明

天兵天将8个小时后回来，孙悟空吃掉所有蟠桃的最小速度4。

  1. 第1小时全部吃完第一棵树，吃3个，
  2. 第2小时吃4个，第二棵树剩7个，
  3. 第3小时吃4个，第二棵树剩3个，
  4. 第4小时吃3个，第二棵树吃完，
  5. 第5小时吃4个，第三棵树剩2个，
  6. 第6小时吃2个，第三棵树吃完，
  7. 第7小时吃4个，第4棵树剩3个，
  8. 第8小时吃3个，第4棵树吃完。

四、解题思路

题目描述有点复杂，多读几遍不难理解，意思就是：

一个小时只能在一棵桃树上吃，如果吃不完，下一个小时继续吃，如果吃完了，就不吃了，但不能去吃下一颗桃树，要守规矩。

  1. 输入几个数，表示每颗树的桃子数量；
  2. 在H个小时内，以最慢的速度将这些桃子全部吃完。

很明显的回溯问题，一个一个找呗，看哪个速度最合适。

五、Java算法源码

1、从速度1开始回溯，寻找H小时内吃完所有桃子的最小速度

假如孙猴子一小时吃100个桃子最合适，效率有点堪忧。

java">public class Test06 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        // 天兵天将将离开的时间H
        int H = arr[arr.length - 1];

        // 获取每棵数上蟠桃个数
        arr = Arrays.copyOf(arr, arr.length - 1);

        // 从少到多排序
        Arrays.sort(arr);

        // 从速度1开始回溯，寻找H小时内吃完所有桃子的最小速度
        dfs(arr, H, 1);

        System.out.println(minSpeed);
        System.out.println("执行次数：" + num);
    }

    // 记录回溯次数，优化回溯算法
    static int num = 0;
    // 吃完所有桃子的最小速度
    static int minSpeed = 0;

    /**
     * 从速度1开始回溯，寻找H小时内吃完所有桃子的最小速度
     */
    private static void dfs(int[] arr, int H, int K) {
        int times = 0;
        for (int i = 0; i < arr.length; i++) {
            num++;
            // 以速度K吃完每颗桃树的时间
            times += arr[i] / K;
            if (arr[i] % K != 0) {
                times++;
            }
        }

        // 因为速度从小到大递增，当时间 <= H时，即最小速度
        if (times <= H) {
            minSpeed = K;
            return;
        } else {
            // 吃不完，加快速度
            dfs(arr, H, ++K);
        }
    }
}

输入：3 25 6 7 8
输出：7
执行次数：28

2、预测一个最可能的速度

所有桃子的数量除以总时间，得出每小时吃桃子数量，我觉得这个就是比较接近最小速度的最优解。

  1. 如果吃不完，就加快速度；
  2. 如果吃完了，就吃慢一点；
  3. 哈哈
java">public class Test08 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        // 天兵天将将离开的时间H
        int H = arr[arr.length - 1];

        // 获取每棵数上蟠桃个数
        arr = Arrays.copyOf(arr, arr.length - 1);
        // 从少到多排序
        Arrays.sort(arr);

        // 预测最可能速度，优化回溯算法
        int sum = Arrays.stream(arr).sum();
        int possible = sum % H == 0 ? sum / H : sum / H + 1;

        System.out.println("预测最可能速度：" + possible);

        // 从最可能速度开始回溯，寻找H小时内吃完所有桃子的最小速度
        dfs(arr, H, possible);

        System.out.println(minSpeed);
        System.out.println("执行次数：" + num);
    }

    // 记录回溯次数，优化回溯算法
    static int num = 0;
    // 吃完所有桃子的最小速度
    static int minSpeed = 0;
    // 上一次吃完所有桃子的速度
    static int preSpeed = 0;

    private static void dfs(int[] arr, int H, int K) {
        int times = 0;
        for (int i = 0; i < arr.length; i++) {
            num++;
            // 以速度K吃完每颗桃树的时间
            times += arr[i] / K;
            if (arr[i] % K != 0) {
                times++;
            }
        }

        // 吃不完，加快速度
        if (times > H) {
            // 如果上次已经吃完，则上次吃完的速度即最小速度
            if (preSpeed != 0) {
                minSpeed = preSpeed;
                return;
            }
            dfs(arr, H, ++K);
        } else if (times < H) {// 吃完了，再吃慢一点
            preSpeed = K;
            dfs(arr, H, --K);
        } else {// 刚好吃完，返回最小速度
            minSpeed = K;
            return;
        }
    }
}

输入：3 25 6 7 8
输出：7
预测最可能速度：6
执行次数：12

3、一切都靠猜 + 回溯，有点太小儿科了，通过二分查找正统一下

java">public class Test09 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        // 天兵天将将离开的时间H
        int H = arr[arr.length - 1];

        // 获取每棵数上蟠桃个数
        arr = Arrays.copyOf(arr, arr.length - 1);
        // 从少到多排序
        Arrays.sort(arr);

        int left = 1;
        int right = arr[arr.length - 1];
        while (left < right) {
            int mid = (left + right) / 2;
            // 吃完了，还能慢一点
            if (dfs(arr, H, mid)) {
                right = mid;
            } else {// 没吃完，吃快一点
                left = mid + 1;
            }
        }
        System.out.println(left);
        System.out.println("执行次数：" + num);
    }

    // 记录回溯次数，优化回溯算法
    static int num = 0;
    // 上一次吃完所有桃子的速度
    static int preSpeed = 0;

    private static boolean dfs(int[] arr, int H, int K) {
        int times = 0;
        for (int i = 0; i < arr.length; i++) {
            num++;
            // 以速度K吃完每颗桃树的时间
            times += arr[i] / K;
            if (arr[i] % K != 0) {
                times++;
            }
        }
        return times <= H;
    }
}

输入：3 25 6 7 8
输出：7
执行次数：16

通过对比，还是预测一个最可能的速度效率最高，嘿嘿~

六、效果展示

1、输入

3 25 6 7 8

2、输出

7

3、说明

在这里插入图片描述


🏆下一篇：华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 C卷 200分）

🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷+C卷）

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

在这里插入图片描述


http://www.niftyadmin.cn/n/5457658.html

相关文章

算法日记————对顶堆（4道题）

算法日记————对顶堆（4道题）

对顶堆的作用主要在于动态维护第k大的数字&#xff0c;考虑使用两个优先队列&#xff0c;一个大9999999999根堆一个小根堆&#xff0c;小根堆维护大于等于第k大的数字的数&#xff0c;它的堆顶就是堆内最小&#xff0c;第k大的数字&#xff0c;另外一个大根堆维护小于等于k的数…
阅读更多...
基于Hive大数据分析springboot为后端以及vue为前端的的民宿系

基于Hive大数据分析springboot为后端以及vue为前端的的民宿系

标题基于Hive大数据分析springboot为后端以及vue为前端的的民宿系 本文介绍了如何利用Hive进行大数据分析，并结合Spring Boot和Vue构建了一个民宿管理系统。该民民宿管理系统包含用户和管理员登陆注册的功能，发布下架酒店信息，模糊搜索，酒店详情信息展示，收藏以及对收藏的…
阅读更多...
vue3从精通到入门6：v-memo指令

vue3从精通到入门6：v-memo指令

v-memo是一个用于优化组件渲染性能的指令。它允许你根据某个条件来缓存组件的虚拟 DOM 树&#xff0c;从而在条件没有变化时避免不必要的重新渲染。这对于那些接收大量 props 且渲染成本较高的组件来说非常有用。 用法 v-memo 指令接受一个表达式或一个数组作为参数&#xff0…
阅读更多...
Qt中常用宏定义

Qt中常用宏定义

Qt中常用宏定义 一、Q_DECLARE_PRIVATE(Class)二、Q_DECLARE_PRIVATE_D(Dptr, Class)三、Q_DECLARE_PUBLIC(Class)四、Q_D(Class) 和 Q_Q(Class) 一、Q_DECLARE_PRIVATE(Class) #define Q_DECLARE_PRIVATE(Class) inline Class##Private* d_func() { # 此处的 d_ptr 是属于QOb…
阅读更多...
基于双vip+GTID的半同步主从复制集群项目（MySQL集群）

基于双vip+GTID的半同步主从复制集群项目（MySQL集群）

项目标题&#xff1a;基于keepalivedGTID的半同步主从复制MySQL集群 准备七台机器&#xff0c;其中有四台时MySQL服务器&#xff0c;搭建主从复制的集群&#xff0c;一个master&#xff0c;2个slave服务器&#xff0c;一个延迟备份服务器。同时延迟备份服务器也可以充当异地备…
阅读更多...
C++中vector的模拟实现

C++中vector的模拟实现

一、vector.h #pragma once #include<iostream> #include<assert.h> #include<string> namespace bit {template<class T>class vector{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;iterator begin(…
阅读更多...
ABAP 字段类型不一样导致相加之后金额错误

ABAP 字段类型不一样导致相加之后金额错误

文章目录 ABAP 字段类型不一样导致相加之后金额错误写在前面的总结示例程序1汇总MSEG表和MLDOC表 ABAP 字段类型不一样导致相加之后金额错误 写在前面的总结 如果需要不同底表的字段相加的值&#xff0c;那么最好是根据条件去分别算出那些值放在临时内表里面&#xff0c;再去…
阅读更多...
微服务demo（二）nacos服务注册与集中配置

微服务demo（二）nacos服务注册与集中配置

环境&#xff1a;nacos1.3.0 一、服务注册 1、pom&#xff1a; 移步spring官网https://spring.io&#xff0c;查看集成Nacos所需依赖 找到对应版本点击进入查看集成说明 然后再里面找到集成配置样例&#xff0c;这里只截一张&#xff0c;其他集成内容继续向下找 我的&#x…
阅读更多...
最新文章

Copyright @ 2022~2023