小蓝xlanll

这个屌丝很懒，什么也没留下！

热门标签

【Py/Java/C++三种语言OD独家2024D卷真题】20天拿下华为OD笔试之【二分查找】2024D-机器人搬砖【欧弟算法】全网注释最详细分类最全的华为OD真题题解_华为od2024d卷

作者：小蓝xlanll | 2024-05-16 03:51:38

踩

华为od2024d卷

从2024年4月15号开始，OD机考全部配置为2024D卷。
注意两个关键点：

会遇到C卷复用题。虽然可能存在幸存者偏差，但肯定还会有一大部分的旧题。
现在又支持做完题目之后倒回去改了。就是可以先做200的再做100的，然后可以反复提交。

在这里插入图片描述

有LeetCode算法/华为OD考试扣扣交流群可加 948025485
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
绿色聊天软件戳 od1336了解算法冲刺训练

题目描述与示例

题目描述

机器人搬砖，一共有N堆砖存放在N个不同的仓库中，第i堆砖中有bricks[i]块砖头，要求在8小时内搬完。机器人每小时能搬砖的数量取决于有多少能量格，机器人一个小时中只能在一个仓库中搬砖，机器人的能量格每小时补充一次且能量格只在这一个小时有效，为使得机器人损耗最小化，尽量减小每次补充的能量格数。

为了保障在8小时内能完成搬砖任务，请计算每小时给机器人充能的最小能量格数。

备注:

1、无需考虑机器人补充能量格的耗时

2、无需考虑机器人搬砖的耗时

3、机器人每小时补充能量格只在这一个小时中有效。

输入描述

程序输入为"30 12 25 8 19"一个整数数组，数组中的每个数字代表第i堆砖的个数，每堆砖的个数不超过100

输出描述

输出在8小时内完成搬砖任务，机器人每小时最少需要充多少个能量格；如果8个小时内无论如何都完成不了任务，则输出"-1"

示例

输入

30 12 25 8 19
1

输出

15
1

说明

解题思路

注意，本题和LeetCode875.爱吃香蕉的珂珂、【二分查找】2023C-孙悟空吃蟠桃几乎完全一致。甚至更加简单，因为时间固定为8

代码

解法一：左闭右开写法

python

# 题目：【二分查找】2023C-机器人搬砖
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：二分查找
# 代码看不懂的地方，请直接在群上提问
# 相关题目：LeetCode875.爱吃香蕉的珂珂


# 导入向上取整函数ceil，用于后续的计算
from math import ceil


# 输入每一个仓库的砖块数目
nums = list(map(int, input().split()))
# 设置搬砖时间上限为8h
h = 8

# 计算花费在速度k的条件下，所花费的时间h的函数
def cal_hour_used(nums, k):
    return sum(ceil(p / k) for p in nums)


# 二分查找求解问题的函数
def minEatingSpeed(nums, h):
    # 左闭右开区间，right取最大的那一堆的值再+1
    left, right = 1, max(nums) + 1
    # left和right相等时，区间消失，退出循环
    while left < right:
        mid = (left + right) // 2
        # 花费时间太少，速度偏大，速度还可以减小，
        # 搜索区间向左折半，right可以向左移动
        if cal_hour_used(nums, mid) <= h:
            right = mid
        else:
            left = mid + 1
    # 退出循环时，left和right是恰好满足条件cal_hour_used(nums, mid) <= h的速度
    # 返回left或right均可
    return left


# 如果nums的长度已经大于h，一定无法在h小时内搬完所有砖
# 直接输出-1
if len(nums) > h:
    print(-1)
# 否则进行二分，输出答案
else:
    print(minEatingSpeed(nums, h))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

java

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split(" ");
        int[] nums = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            nums[i] = Integer.parseInt(input[i]);
        }
        int h = 8;
        if (nums.length > h){
            System.out.println(-1);
        } else {
            int result = minEatingSpeed(nums, h);
            System.out.println(result);  
        }

    }

    // 计算花费在速度k的条件下，所花费的时间h的函数
    public static int calHourUsed(int[] nums, int k) {
        int hours = 0;
        for (int p : nums) {
            hours += Math.ceil((double) p / k);
        }
        return hours;
    }

    // 二分查找求解问题的函数
    public static int minEatingSpeed(int[] nums, int h) {
        // 左闭右开区间，right取最大的那一堆的值再+1
        int left = 1, right = 0;
        for (int num : nums) {
            right = Math.max(right, num);
        }
        right += 1;
        // left和right相等时，区间消失，退出循环
        while (left < right) {
            // 花费时间太少，速度偏大，速度还可以减小，
            // 搜索区间向左折半，right可以向左移动
            int mid = left + (right - left) / 2;
            if (calHourUsed(nums, mid) <= h) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        // 退出循环时，left和right是恰好满足条件cal_hour_used(nums, mid) <= h的速度
        // 返回left或right均可
        return left;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

cpp

#include <iostream>
#include <vector>
#include <cmath>
#include <sstream>

using namespace std;

// 计算花费在速度k的条件下，所花费的时间h的函数
int calHourUsed(vector<int>& nums, int k) {
    int hours = 0;
    for (int p : nums) {
        hours += ceil((double)p / k);
    }
    return hours;
}

// 二分查找求解问题的函数
int minEatingSpeed(vector<int>& nums, int h) {
    // 左闭右开区间，right取最大的那一堆的值再+1
    int left = 1, right = 0;
    for (int num : nums) {
        right = max(right, num);
    }
    right += 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (calHourUsed(nums, mid) <= h) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    // 退出循环时，left和right是恰好满足条件cal_hour_used(nums, mid) <= h的速度
    // 返回left或right均可
    return left;
}

int main() {
    vector<int> nums;
    string input;
    getline(cin, input);
    istringstream iss(input);
    int num;
    while (iss >> num) {
        nums.push_back(num);
    }
    int h = 8;
    if (nums.size() > h){
        cout << -1 << endl;
    } else {
        int result = minEatingSpeed(nums, h);
        cout << result << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

解法二：左闭右闭写法

python

# 题目：【二分查找】2023C-机器人搬砖
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：二分查找
# 代码看不懂的地方，请直接在群上提问
# 相关题目：LeetCode875.爱吃香蕉的珂珂


# 导入向上取整函数ceil，用于后续的计算
from math import ceil


# 输入每一个仓库的砖块数目
nums = list(map(int, input().split()))
# 设置搬砖时间上限为8h
h = 8

# 计算花费在速度k的条件下，所花费的时间h的函数
def cal_hour_used(nums, k):
    return sum(ceil(p / k) for p in nums)


# 二分查找求解问题的函数
def minEatingSpeed(nums, h):
    # 左闭右闭区间，right取最大的那一堆的值
    left, right = 1, max(nums)
    # left严格大于right时，区间消失，退出循环
    while left <= right:
        mid = (left + right) // 2
        # 花费时间太少，速度偏大，速度还可以减小，
        # 搜索区间向左折半，right可以向左移动
        if cal_hour_used(nums, mid) <= h:
            right = mid - 1
        else:
            left = mid + 1
    # 退出循环时，存在left = right+1
    # left是恰好满足条件cal_hour_used(nums, mid) <= h的速度
    # right是恰好满足条件cal_hour_used(nums, mid) > h的速度
    # 返回left或right+1均可
    return left


# 如果nums的长度已经大于h，一定无法在h小时内搬完所有砖
# 直接输出-1
if len(nums) > h:
    print(-1)
# 否则进行二分，输出答案
else:
    print(minEatingSpeed(nums, h))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

java

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split(" ");
        int[] nums = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            nums[i] = Integer.parseInt(input[i]);
        }
        int h = 8;
        if (nums.length > h){
            System.out.println(-1);
        } else {
            int result = minEatingSpeed(nums, h);
            System.out.println(result);  
        }
    }

    // 计算花费在速度k的条件下，所花费的时间h的函数
    public static int calHourUsed(int[] nums, int k) {
        int hours = 0;
        for (int p : nums) {
            hours += Math.ceil((double) p / k);
        }
        return hours;
    }

    // 二分查找求解问题的函数
    public static int minEatingSpeed(int[] nums, int h) {
        // 左闭右闭区间，right取最大的那一堆的值
        int left = 1, right = 0;
        for (int num : nums) {
            right = Math.max(right, num);
        }
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 花费时间太少，速度偏大，速度还可以减小，
            // 搜索区间向左折半，right可以向左移动
            if (calHourUsed(nums, mid) <= h) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // 退出循环时，存在left = right+1
        // left是恰好满足条件calHourUsed(nums, mid) <= h的速度
        // right是恰好满足条件calHourUsed(nums, mid) > h的速度
        // 返回left或right+1均可
        return left;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

cpp

#include <iostream>
#include <vector>
#include <cmath>
#include <sstream>

using namespace std;

// 计算花费在速度k的条件下，所花费的时间h的函数
int calHourUsed(vector<int>& nums, int k) {
    int hours = 0;
    for (int p : nums) {
        hours += ceil((double)p / k);
    }
    return hours;
}

// 二分查找求解问题的函数
int minEatingSpeed(vector<int>& nums, int h) {
    // 左闭右闭区间，right取最大的那一堆的值
    int left = 1, right = 0;
    for (int num : nums) {
        right = max(right, num);
    }
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // 花费时间太少，速度偏大，速度还可以减小，
        // 搜索区间向左折半，right可以向左移动
        if (calHourUsed(nums, mid) <= h) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    // 退出循环时，存在left = right+1
    // left是恰好满足条件calHourUsed(nums, mid) <= h的速度
    // right是恰好满足条件calHourUsed(nums, mid) > h的速度
    // 返回left或right+1均可
    return left;
}

int main() {
    vector<int> nums;
    string input;
    getline(cin, input);
    istringstream iss(input);
    int num;
    while (iss >> num) {
        nums.push_back(num);
    }
    int h = 8;
    if (nums.size() > h){
        cout << -1 << endl;
    } else {
        int result = minEatingSpeed(nums, h);
        cout << result << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

时空复杂度

时间复杂度：O(NlogN)。其中N为nums数组长度。
空间复杂度：O(1)。

华为OD算法/大厂面试高频题算法练习冲刺训练

华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务300+同学成功上岸！
课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！
60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
可查看链接大厂真题汇总 & OD真题汇总(持续更新)
绿色聊天软件戳 od1336了解更多

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/576729

【Py/Java/C++三种语言OD独家2024D卷真题】20天拿下华为OD笔试之【二分查找】2024D-机器人搬砖【欧弟算法】全网注释最详细分类最全的华为OD真题题解_华为od2024d卷

文章目录

题目描述与示例

题目描述

输入描述

输出描述

示例

输入

输出

说明

解题思路

代码

解法一：左闭右开写法

python

java

cpp

解法二：左闭右闭写法

python

java

cpp

时空复杂度

华为OD算法/大厂面试高频题算法练习冲刺训练