题目描述
机器人搬砖，一共有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
