华为OD机试 - 机器人搬砖（Java & JS & Python & C & C++）

题目描述

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

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

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

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

  输入描述

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

  输出描述

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

  用例

  输入	30 12 25 8 19
  输出	15
  说明	无

  输入	10 12 25 8 19 8 6 4 17 19 20 30
  输出	-1
  说明	砖的堆数为12堆存放在12个仓库中，机器人一个小时内只能在一个仓库搬砖，不可能完成任务。

  题目解析

  本题有个关键说明：

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

  另外：

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

  机器人一个小时只能在一个仓库干活，那么在8小时内，机器人最多干完8个仓库。

  • 如果bricks.length > 8，那么机器人肯定不可能在8小时内干完。
  • 如果bricks.length (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 > 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 > 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 > 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 #include #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  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  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;}

    C++算法源码

    #include using namespace std;/*! * * @param energy 每小时可以使用的能量块数量 * @param limit 限制几小时内干完 * @param bricks 要搬几堆砖头 * @return 是否可以在limit小时内已指定energy能量办完所有bricks */bool check(int energy, int limit, vector &bricks) {    // 已花费的小时数    int cost = 0;    for (const auto &brick: bricks) {        cost += brick / energy + (brick % energy > 0 ? 1 : 0);        // 如果搬砖过程中发现，花费时间已经超过限制，则直接返回false        if (cost > limit) {            return false;        }    }    return true;}int solution(vector &bricks) {    // 机器人每小时只能在一个仓库干活，因此给定8小时，最多只能搬完8个仓库，如果仓库数量超过8，那么肯定干不完    if (bricks.size() > 8) {        return -1;    }    // 每小时最多需要的能量块    int max = *max_element(bricks.begin(), bricks.end());    // 如果有8个仓库，那么只能1个小时干1个仓库，且机器人每小时需要能量至少是max(bricks)，这样才能保证1个小时内把最多砖块的那个仓库搬完    if (bricks.size() == 8) {        return max;    }    // 每小时最少需要的能量块    int min = 1;    // 如果仓库数少于8个，那么此时每小时能量max(bricks)必然能在8小时内搬完所有仓库，但不是最优解    int ans = max;    // 二分法    while (min > 1;        if (check(mid, 8, bricks)) {            // 如果每小时充mid格能量，就能在8小时内，搬完所有砖头，则mid就是一个可能解            ans = mid;            // 但mid不一定是最优解，因此继续尝试更小的能量块            max = mid - 1;        } else {            // 如果每小时充mid能量块，无法在8小时能完成工作，则说明每天能量块充少了，下次应该尝试充更多能量块            min = mid + 1;        }    }    return ans;}int main() {    vector bricks;    int tmp;    while (cin >> tmp) {        bricks.emplace_back(tmp);    }    cout