(新卷,100分)- 机器人搬砖（Java JS Python C）

(新卷,100分)- 机器人搬砖（Java & JS & Python & C）

题目描述

机器人搬砖，一共有 N 堆砖存放在 N 个不同的仓库中，第 i 堆砖中有 bricks[i] 块砖头，要求在 8 小时内搬完。

机器人每小时能搬砖的数量取决于有多少能量格，机器人一个小时中只能在一个仓库中搬砖，机器人的能量格只在这一个小时有效，为使得机器人损耗最小化，应尽量减小每次补充的能量格数。

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

• 无需考虑机器人补充能力格的耗时；
• 无需考虑机器人搬砖的耗时；
• 机器人每小时补充能量格只在这一个小时中有效；

输入描述

第一行为一行数字，空格分隔

输出描述

机器人每小时最少需要充的能量格，若无法完成任务，输出 -1

用例

题目解析

本题有个关键说明：

机器人一个小时中只能在一个仓库中搬砖

另外：

机器人搬砖，一共有 N 堆砖存放在 N 个不同的仓库中，第 i 堆砖中有 bricks[i] 块砖头，要求在 8 小时内搬完

机器人每小时只能在一个仓库工作，因此在8小时内最多可以完成8个仓库的任务。

当bricks.length > 8时，机器人显然无法在8小时内完成所有工作。 当bricks.length <= 8时，我们可以使用二分法来确定最小每小时充电量。

设机器人每小时需要k单位能量：

• 若只有一个仓库，砖块应平均分配到8小时内搬运，以确保每小时搬运量最少、能耗最低。例如当砖块数为1时，每小时只需1单位能量。因此k的最小值为1。
• 若有8个仓库，k的最小值应为max(bricks)，以确保能完成砖块最多的仓库。因此k的最大值为max(bricks)。

确定k的范围后，通过二分法进行验证：

• 若mid值能满足8小时内完成所有仓库，则记录该解，并尝试寻找更优解，即右边界调整为mid-1
• 若mid值不能满足要求，说明能量不足，需提高充电量，即左边界调整为mid+1

JavaScript算法源码

const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; void (async function () { const bricks = (await readline()).split(" ").map(Number); console.log(getResult(bricks)); })(); function getResult(bricks) { // 机器人每小时只能在一个仓库干活，因此给定8小时，最多只能搬完8个仓库，如果仓库数量超过8，那么肯定干不完 if (bricks.length > 8) { return -1; } // 每小时最多需要的能量块 let max = Math.max(...bricks); // 如果有8个仓库，那么只能1个小时干1个仓库，且机器人每小时需要能量至少是max(bricks)，这样才能保证1个小时内把最多砖块的那个仓库搬完 if (bricks.length == 8) { return max; } // 如果仓库数少于8个，那么此时每小时能量max(bricks)必然能在8小时内搬完所有仓库，但不是最优解 let ans = max; // 每小时最少需要的能量块 let min = 1; // 二分法 while (min <= max) { // 取中间值 const mid = (min + max) >> 1; if (check(mid, 8, bricks)) { // 如果每小时充mid格能量，就能在8小时内，搬完所有砖头，则mid就是一个可能解 ans = mid; // 但mid不一定是最优解，因此继续尝试更小的能量块 max = mid - 1; } else { // 如果每小时充mid能量块，无法在8小时能完成工作，则说明每天能量块充少了，下次应该尝试充更多能量块 min = mid + 1; } } return ans; } /** * * @param {*} energy 每小时可以使用的能量块数量 * @param {*} limit 限制几小时内干完 * @param {*} bricks 要搬的几堆砖头 * @returns 是否可以在limit小时内已指定energy能量搬完所有bricks */ function check(energy, limit, bricks) { // 已花费的小时数 let cost = 0; for (let brick of bricks) { cost += Math.ceil(brick / energy); // 如果搬砖过程中发现，花费时间已经超过限制，则直接返回false if (cost > limit) { return false; } } return true; }

Java算法源码

import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[] bricks = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray(); System.out.println(getResult(bricks)); } public static int getResult(int[] bricks) { // 机器人每小时只能在一个仓库干活，因此给定8小时，最多只能搬完8个仓库，如果仓库数量超过8，那么肯定干不完 if (bricks.length > 8) { return -1; } // 每小时最多需要的能量块 int max = Arrays.stream(bricks).max().orElse(0); // 如果有8个仓库，那么只能1个小时干1个仓库，且机器人每小时需要能量至少是max(bricks)，这样才能保证1个小时内把最多砖块的那个仓库搬完 if (bricks.length == 8) { return max; } // 如果仓库数少于8个，那么此时每小时能量max(bricks)必然能在8小时内搬完所有仓库，但不是最优解 int ans = max; // 每小时最少需要的能量块 int min = 1; // 二分法 while (min <= max) { // 取中间值 int mid = (min + max) >> 1; if (check(mid, 8, bricks)) { // 如果每小时充mid格能量，就能在8小时内，搬完所有砖头，则mid就是一个可能解 ans = mid; // 但mid不一定是最优解，因此继续尝试更小的能量块 max = mid - 1; } else { // 如果每小时充mid能量块，无法在8小时能完成工作，则说明每天能量块充少了，下次应该尝试充更多能量块 min = mid + 1; } } return ans; } /** * @param energy 每小时可以使用的能量块数量 * @param limit 限制几小时内干完 * @param bricks 要搬几堆砖头 * @return 是否可以在limit小时内已指定energy能量办完所有bricks */ public static boolean check(int energy, int limit, int[] bricks) { // 已花费的小时数 int cost = 0; for (int brick : bricks) { cost += brick / energy + (brick % energy > 0 ? 1 : 0); // 如果搬砖过程中发现，花费时间已经超过限制，则直接返回false if (cost > limit) { return false; } } return true; } }

Python算法源码

import math # 输入获取 bricks = list(map(int, input().split())) def check(energy, limit): """ :param energy: 每小时可以使用的能量块数量（搬一块砖消耗一块能量） :param limit: 限制几小时内干完 :return: 是否可以在limit小时内搬完所有bricks """ cost = 0 # 已花费的小时数 for brick in bricks: cost += math.ceil(brick / energy) # 如果搬砖过程中发现，花费时间已经超过限制，则直接返回false if cost > limit: return False return True # 算法入口 def getResult(): # 机器人每小时只能在一个仓库干活，因此给定8小时，最多只能搬完8个仓库，如果仓库数量超过8，那么肯定干不完 if len(bricks) > 8: return -1 # 每小时最多需要的能量块 maxEnergy = max(bricks) # 如果有8个仓库，那么只能1个小时干1个仓库，且机器人每小时需要能量至少是max(bricks)，这样才能保证1个小时内把最多砖块的那个仓库搬完 if len(bricks) == 8: return maxEnergy # 如果仓库数少于8个，那么此时每小时能量max(bricks)必然能在8小时内搬完所有仓库，但不是最优解 ans = maxEnergy # 每小时最少需要的能量块 minEnergy = 1 # 二分法 while minEnergy <= maxEnergy: # 取中间值 mid = (minEnergy + maxEnergy) >> 1 if check(mid, 8): # 如果每小时充mid格能量，就能在8小时内，搬完所有砖头，则mid就是一个可能解 ans = mid # 但mid不一定是最优解，因此继续尝试更小的能量块 maxEnergy = mid - 1 else: # 如果每小时充mid能量块，无法在8小时能完成工作，则说明每天能量块充少了，下次应该尝试充更多能量块 minEnergy = mid + 1 return ans # 算法调用 print(getResult())

C算法源码

#include <stdio.h> #include <limits.h> #define MAX(a, b) ((a) > (b) ? (a) : (b)) #define MAX_SIZE 100000 /*! * * @param energy 每小时可以使用的能量块数量 * @param limit 限制几小时内干完 * @param bricks 要搬走的砖 * @param bricks_size 砖的堆数 * @return 是否可以在limit小时内搬完所有bricks */ int check(int energy, int limit, const int bricks[], int bricks_size) { // 已花费的天数 int cost = 0; for (int i = 0; i < bricks_size; i++) { cost += bricks[i] / energy + (bricks[i] % energy > 0 ? 1 : 0); // 如果搬砖过程中发现，花费时间已经超过限制，则直接返回false if (cost > limit) { return 0; } } return 1; } int getResult(const int bricks[], int bricks_size) { // 机器人每小时只能在一个仓库干活，因此给定8小时，最多只能搬完8个仓库，如果仓库数量超过8，那么肯定干不完 if (bricks_size > 8) { return -1; } // 每小时最多需要的能量块 int max = INT_MIN; for (int i = 0; i < bricks_size; i++) { max = MAX(max, bricks[i]); } // 如果有8个仓库，那么只能1个小时干1个仓库，且机器人每小时需要能量至少是max(bricks)，这样才能保证1个小时内把最多砖块的那个仓库搬完 if(bricks_size == 8) { return max; } // 如果仓库数少于8个，那么此时每小时能量max(bricks)必然能在8小时内搬完所有仓库，但不是最优解 int ans = max; // 每小时最少需要的能量块 int min = 1; // 二分法 while (min <= max) { // 取中间值 int mid = (min + max) >> 1; if (check(mid, 8, bricks, bricks_size)) { // 如果每小时充mid格能量，就能在8小时内，搬完所有砖头，则mid就是一个可能解 ans = mid; // 但mid不一定是最优解，因此继续尝试更小的能量块 max = mid - 1; } else { // 如果每小时充mid能量块，无法在8小时能完成工作，则说明每天能量块充少了，下次应该尝试充更多能量块 min = mid + 1; } } return ans; } int main() { int bricks[MAX_SIZE]; int bricks_size = 0; while (scanf("%d", &bricks[bricks_size++])) { if (getchar() != ' ') break; } printf("%d\n", getResult(bricks, bricks_size)); return 0; }