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

03-07 1167阅读

题目描述

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

华为OD机试 - 机器人搬砖（Java & JS & Python & C & C++）
（图片来源网络，侵删）

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

为了保障在 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
VPS购买请点击我

文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。

相关阅读

目录[+]