【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 机器人搬砖(100分)

本文主要是介绍【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 机器人搬砖(100分) - 三语言AC题解(Python/Java/Cpp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

💻 ACM银牌🥈| 多次AK大厂笔试｜编程一对一辅导

👏 感谢大家的订阅➕ 和喜欢💗

📎在线评测链接

https://app5938.acapp.acwing.com.cn/contest/2/problem/OD1061
🌍 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系清隆解锁～

🍓OJ题目截图

在这里插入图片描述

文章目录

- 📎在线评测链接
- 🍓OJ题目截图
- 🎧 机器人搬砖
- - 问题描述
  - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 样例输入
  - 样例输出
  - 数据范围
  - 题解
  - 参考代码

🎧 机器人搬砖

问题描述

K小姐的仓库里有 $N$ 堆砖块，第 $i$ 堆中有 $b r i c k s [i]$ 块砖。她的机器人需要在 $8$ 小时内将所有砖块搬完。机器人每小时可以搬运的砖块数量取决于它的能量格数。为了尽量减少机器人的损耗，K小姐希望每次给机器人充能时，能量格数尽可能少。

已知机器人每小时只能在一个仓库搬砖，且每次充能获得的能量格只在当前小时内有效。请你帮助K小姐计算出，为了在 $8$ 小时内完成搬砖任务，每次给机器人充能时最少需要多少能量格。

输入格式

输入一行，包含若干个用空格分隔的正整数，分别表示每堆砖块的数量，即 $b r i c k s [1]$ 到 $b r i c k s [N]$ 。

输出格式

输出一个整数，表示每次给机器人充能时最少需要的能量格数。

若 $8$ 小时内无法完成搬砖任务，则输出 $- 1$ 。

样例输入

30 12 25 8 19

样例输出

样例输入

10 12 25 8 19 8 6 4 17 19 20 30

样例输出

-1

数据范围

$\le N \le 100$
$\le bricks[i] \le 100$

题解

本题可以使用二分查找的思路来解决。我们可以把每次充能的能量格数作为二分查找的目标值，判断在该能量格数下是否能在 $8$ 小时内完成搬砖任务。

具体做法如下：

初始化二分查找的区间为 $[1, ma x (b r i c k s)]$ ，其中 $ma x (b r i c k s)$ 表示所有堆砖块数量的最大值。
在每次二分查找的过程中，取区间的中点作为当前的能量格数 $mi d$ 。
遍历每堆砖块，计算出搬完所有砖块需要的总时间 $n u m$ ，其中搬完第 $i$ 堆砖块需要的时间为 $\lceil \frac{bricks[i]}{mid} \rceil$ 。
如果 $\le 8$ ，说明当前的能量格数 $mi d$ 可以满足要求，我们继续在 $[1, mi d]$ 的范围内进行二分查找；否则，我们在 $[mi d + 1, ma x (b r i c k s)]$ 的范围内进行二分查找。
当二分查找的区间左右端点相等时，搜索结束，返回最终的能量格数即可。
如果搜索结束时，最终的能量格数仍无法满足在 $8$ 小时内完成搬砖任务，就返回 $- 1$ 。

参考代码

Python

def min_energy(bricks):n = len(bricks)if n > 8:return -1left, right = 1, max(bricks)while left < right:mid = (left + right) // 2num = sum((x + mid - 1) // mid for x in bricks)if num <= 8:right = midelse:left = mid + 1return leftbricks = list(map(int, input().split()))
print(min_energy(bricks))

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 n = input.length;int[] bricks = new int[n];for (int i = 0; i < n; i++) {bricks[i] = Integer.parseInt(input[i]);}System.out.println(minEnergy(bricks));}private static int minEnergy(int[] bricks) {int n = bricks.length;if (n > 8) {return -1;}int left = 1, right = 0;for (int x : bricks) {right = Math.max(right, x);}while (left < right) {int mid = left + (right - left) / 2;int num = 0;for (int x : bricks) {num += (x + mid - 1) / mid;}if (num <= 8) {right = mid;} else {left = mid + 1;}}return left;}
}

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int minEnergy(vector<int>& bricks) {int n = bricks.size();if (n > 8) {return -1;}int left = 1, right = *max_element(bricks.begin(), bricks.end());while (left < right) {int mid = left + (right - left) / 2;int num = 0;for (int x : bricks) {num += (x + mid - 1) / mid;}if (num <= 8) {right = mid;} else {left = mid + 1;}}return left;
}int main() {string input;getline(cin, input);vector<int> bricks;size_t pos = 0;while ((pos = input.find(' ')) != string::npos) {bricks.push_back(stoi(input.substr(0, pos)));input.erase(0, pos + 1);}bricks.push_back(stoi(input));cout << minEnergy(bricks) << endl;return 0;
}