华为OD机试 - 机器人搬砖（Java & JS & Python & C & 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 格能量

1. 如果只有一个仓库一堆砖，那么这堆砖就可以平分到8小时内搬，这样才能保证每小时搬最少的砖，消耗最少的能量，即每小时可以充最少的能量。如果这堆砖头足够少，比如只有1块，那么此时机器人每小时只需要充1块能量即可。因此 k 的最小值取 1。
2. 如果有8个仓库，那么机器人每小时的能量格数至少就是 max(bricks)，这样才能保证一个小时干完砖头数量最多的那个仓库。因此 k 的最大值取max(bricks)。

求出 k 的取值范围后，我们可以通过二分取中值的方式，不停尝试可能解mid：

• 如果mid能量块可以满足8小时内搬完所有仓库，那么mid就是一个可能解，但不一定是最优解，此时我们应该尝试充更少的能量，即缩小k的右边界范围到 = mid - 1
• 如果mid能量块不能满足8小时内搬完所有仓库，那么说明每小时充mid能力太少了，我们应该尝试充更多能量，即增大k的左边界范围到 = 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;
}

C++算法源码

#include <bits/stdc++.h>
using namespace std;

/*!
 *
 * @param energy 每小时可以使用的能量块数量
 * @param limit 限制几小时内干完
 * @param bricks 要搬几堆砖头
 * @return 是否可以在limit小时内已指定energy能量办完所有bricks
 */
bool check(int energy, int limit, vector<int> &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<int> &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 <= 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;
}

int main() {
    vector<int> bricks;

    int tmp;
    while (cin >> tmp) {
        bricks.emplace_back(tmp);
    }

    cout << solution(bricks) << endl;

    return 0;
}