最新华为OD机试真题-机器人搬砖(100分)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解
👏 感谢大家的订阅➕ 和 喜欢💗
📎在线评测链接
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁~
🍓OJ题目截图
🎧 机器人搬砖
问题描述
K小姐的仓库里有 堆砖块,第 堆中有 块砖。她的机器人需要在 小时内将所有砖块搬完。机器人每小时可以搬运的砖块数量取决于它的能量格数。为了尽量减少机器人的损耗,K小姐希望每次给机器人充能时,能量格数尽可能少。
已知机器人每小时只能在一个仓库搬砖,且每次充能获得的能量格只在当前小时内有效。请你帮助K小姐计算出,为了在 小时内完成搬砖任务,每次给机器人充能时最少需要多少能量格。
输入格式
输入一行,包含若干个用空格分隔的正整数,分别表示每堆砖块的数量,即 到 。
输出格式
输出一个整数,表示每次给机器人充能时最少需要的能量格数。
若 小时内无法完成搬砖任务,则输出 。
样例输入
30 12 25 8 19
样例输出
15
样例输入
10 12 25 8 19 8 6 4 17 19 20 30
样例输出
-1
数据范围
题解
本题可以使用二分查找的思路来解决。我们可以把每次充能的能量格数作为二分查找的目标值,判断在该能量格数下是否能在 小时内完成搬砖任务。
具体做法如下:
-
初始化二分查找的区间为 ,其中 表示所有堆砖块数量的最大值。
-
在每次二分查找的过程中,取区间的中点作为当前的能量格数 。
-
遍历每堆砖块,计算出搬完所有砖块需要的总时间 ,其中搬完第 堆砖块需要的时间为 。
-
如果 ,说明当前的能量格数 可以满足要求,我们继续在 的范围内进行二分查找;否则,我们在 的范围内进行二分查找。
-
当二分查找的区间左右端点相等时,搜索结束,返回最终的能量格数即可。
-
如果搜索结束时,最终的能量格数仍无法满足在 小时内完成搬砖任务,就返回 。
参考代码
- Python
def min_energy(bricks):
n = len(bricks)
if n > 8:
return -1
left, right = 1, max(bricks)
while left < right:
mid = (left + right) // 2
num = sum((x + mid - 1) // mid for x in bricks)
if num <= 8:
right = mid
else:
left = mid + 1
return left
bricks = 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
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
本专栏给大家提供了华为2024最新华为OD-E/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 部分题目提供OJ在线评测