 - 机器人搬砖 (C++ Python JAVA JS GO))
机器人搬砖
2025华为OD机试 - 华为OD上机考试 100分题型
华为OD机试真题目录点击查看: 华为OD机试真题题库目录｜机考题库 + 算法考点详解
题目描述
机器人搬砖，一共有 N 堆砖存放在 N 个不同的仓库中，第 i 堆砖中有 bricks[i] 块砖头，要求在 8 小时内搬完。
机器人每小时能搬砖的数量取决于有多少能量格，机器人一个小时中只能在一个仓库中搬砖，机器人的能量格只在这一个小时有效，为使得机器人损耗最小化，应尽量减小每次补充的能量格数。
为了保障在 8 小时内能完成搬砖任务，请计算每小时给机器人充能的最小能量格数。
- 无需考虑机器人补充能力格的耗时；
- 无需考虑机器人搬砖的耗时；
- 机器人每小时补充能量格只在这一个小时中有效；
输入描述
第一行为一行数字，空格分隔
输出描述
机器人每小时最少需要充的能量格，若无法完成任务，输出 -1
用例1
输入
30 12 25 8 19输出
15用例2
输入
10 12 25 8 19 8 6 4 17 19 20 30输出
-1说明
砖的堆数为12堆存放在12个仓库中，机器人一个小时内只能在一个仓库搬砖，不可能完成任务。
题解
思路：二分
- 首先进行分类讨论能完成和不能完成的情况:题目要求每小时只能处理一个仓库并且只有八个小时工作时间，分为以下两种情况
- 仓库数量多余8的，肯定不能完成，直接输出-1即可。
- 如果仓库数量小于等于8，则能完成。
- 接下来像这种
在什么限制最少..题型，比较经典就是用二分来实现，这道题就是二分经典题型，二分有个关键就是怎么确定枚举上下边界，对于这道题下边界一个仓库由于可以用多个小时来完成，所以left可以设置为1，上边界right,由于一个时间只能打扫一个仓库，所以right可以设置为最大仓库砖块数。 - 接下来就是二分的基本套路,每次枚举
mid = (left + right) /2,如果能够满足条件则更新res = mid, 否则设置left = mid + 1, 直到left == right结束。 - 至于检验
mid是否可以满足条件的逻辑，就是从前往后枚举仓库，计算每个仓库需要的小时数(count[i] + mid - 1) /mid,累加小时数是否小于等于8
c++
#include<iostream> #include<vector> #include<string> #include <utility> #include <sstream> #include<algorithm> #include<cmath> #include<map> using namespace std; // 通用 切割函数 函数 将字符串str根据delimiter进行切割 vector<int> split(const string& str, const string& delimiter) { vector<int> result; size_t start = 0; size_t end = str.find(delimiter); while (end != string::npos) { result.push_back(stoi(str.substr(start, end - start))); start = end + delimiter.length(); end = str.find(delimiter, start); } // 添加最后一个部分 result.push_back(stoi(str.substr(start))); return result; } bool check(vector<int>& count, int mid) { int hours = 0; for (int i = 0; i < count.size(); i++) { // 每个仓需要时间 hours += (count[i] + mid - 1) / mid; if (hours > 8){ return false; } } return hours <= 8; } int main() { string input; getline(cin, input); vector<int> counts = split(input, " "); int n = counts.size(); // 每小时只能处理一个仓库，超过8小时肯定不能完成 if (n > 8) { cout << -1; return 0; } int left = 1; // 右边界设置为最大数量 int right = 0; for (int i = 0; i < n; i++) { right = max(right, counts[i]); } // 二分 while (left < right) { int mid = (left + right) >> 1; if (check(counts, mid)) { right = mid; } else { left = mid + 1; } } cout << left; return 0; }JAVA
import java.io.*; import java.util.*; public class Main { // 判断在每小时处理 mid 件货物的情况下，是否能在 8 小时内完成 static boolean check(int[] counts, int mid) { int hours = 0; for (int c : counts) { // 向上取整：(c + mid - 1) / mid hours += (c + mid - 1) / mid; if (hours > 8) { return false; } } return true; } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String line = br.readLine(); String[] parts = line.split(" "); int n = parts.length; int[] counts = new int[n]; for (int i = 0; i < n; i++) { counts[i] = Integer.parseInt(parts[i]); } // 每小时只能处理一个仓库，超过 8 个仓库必定失败 if (n > 8) { System.out.print(-1); return; } int left = 1; int right = 0; // 右边界为最大货物量 for (int c : counts) { right = Math.max(right, c); } // 二分查找最小可行解 while (left < right) { int mid = (left + right) >> 1; if (check(counts, mid)) { right = mid; } else { left = mid + 1; } } System.out.print(left); } }Python
importsys# 判断在每小时处理 mid 件货物的情况下# 是否能在 8 小时内完成defcheck(counts,mid):hours=0forcincounts:# 向上取整hours+=(c+mid-1)//midifhours>8:returnFalsereturnTrue# 读取一行输入counts=list(map(int,sys.stdin.readline().split()))n=len(counts)# 每小时只能处理一个仓库，超过 8 个仓库必定失败ifn>8:print(-1)sys.exit(0)left=1right=max(counts)# 二分查找最小可行解whileleft<right:mid=(left+right)//2ifcheck(counts,mid):right=midelse:left=mid+1print(left)JavaScript
constreadline=require('readline');// readline 接收输入constrl=readline.createInterface({input:process.stdin,output:process.stdout});constlines=[];rl.on('line',line=>{lines.push(line.trim());});rl.on('close',()=>{constcounts=lines[0].split(/\s+/).map(Number);constn=counts.length;// 超过 8 个仓库无法完成if(n>8){console.log(-1);return;}letleft=1;letright=Math.max(...counts);// 判断函数functioncheck(mid){lethours=0;for(constcofcounts){// 向上取整hours+=Math.floor((c+mid-1)/mid);if(hours>8){returnfalse;}}returntrue;}// 二分查找while(left<right){constmid=(left+right)>>1;if(check(mid)){right=mid;}else{left=mid+1;}}console.log(left);});Go
packagemainimport("bufio""fmt""os")// 判断在每小时处理 mid 件货物的情况下// 是否能在 8 小时内完成funccheck(counts[]int,midint)bool{hours:=0for_,c:=rangecounts{// 向上取整hours+=(c+mid-1)/midifhours>8{returnfalse}}returntrue}funcmain(){in:=bufio.NewReader(os.Stdin)varcounts[]int// 读取一行所有整数for{varxintif_,err:=fmt.Fscan(in,&x);err!=nil{break}counts=append(counts,x)}n:=len(counts)// 每小时只能处理一个仓库，超过 8 个仓库直接失败ifn>8{fmt.Print(-1)return}left:=1right:=0// 右边界为最大货物量for_,c:=rangecounts{ifc>right{right=c}}// 二分查找最小可行解forleft<right{mid:=(left+right)/2ifcheck(counts,mid){right=mid}else{left=mid+1}}fmt.Print(left)})
