返回目录

题目描述

[机器人搬砖，一共有 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

Python算法源码

import math

# 输入获取
bricks = list(map(int, input().split()))


def is_possible(energy, limit):
    """
    :param energy: 每小时可以使用的能量块数量（搬一块砖消耗一块能量）
    :param limit: 限制几小时内干完
    :return: 是否可以在limit小时内搬完所有bricks
    """
    hours_spent = 0  # 已花费的小时数

    brick_index = 0
    while brick_index < len(bricks):
        hours_spent += math.ceil(bricks[brick_index] / energy)

        # 如果搬砖过程中发现，花费时间已经超过限制，则直接返回false
        if hours_spent > limit:
            return False
  
        brick_index += 1

    return True


# 算法入口
def get_result():
    # 机器人每小时只能在一个仓库干活，因此给定8小时，最多只能搬完8个仓库，如果仓库数量超过8，那么肯定干不完
    if len(bricks) > 8:
        return -1

    # 每小时最多需要的能量块
    max_energy = max(bricks)

    # 如果有8个仓库，那么只能1个小时干1个仓库，且机器人每小时需要能量至少是max(bricks)，这样才能保证1个小时内把最多砖块的那个仓库搬完
    if len(bricks) == 8:
        return max_energy

    # 如果仓库数少于8个，那么此时每小时能量max(bricks)必然能在8小时内搬完所有仓库，但不是最优解
    ans = max_energy

    # 每小时最少需要的能量块
    min_energy = 1

    # 二分法
    while min_energy <= max_energy:
        # 取中间值
        mid = (min_energy + max_energy) // 2

        if is_possible(mid, 8):
            # 如果每小时充mid格能量，就能在8小时内，搬完所有砖头，则mid就是一个可能解
            ans = mid
            # 但mid不一定是最优解，因此继续尝试更小的能量块
            max_energy = mid - 1
        else:
            # 如果每小时充mid能量块，无法在8小时能完成工作，则说明每天能量块充少了，下次应该尝试充更多能量块
            min_energy = mid + 1

    return ans


# 算法调用
print(get_result())

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 is_possible(int energy, int limit, const int bricks[], int bricks_size) {
    // 已花费的天数
    int cost = 0;
    int brick_index = 0;

    while (brick_index < bricks_size) {
        cost += bricks[brick_index] / energy + (bricks[brick_index] % energy > 0 ? 1 : 0);

        // 如果搬砖过程中发现，花费时间已经超过限制，则直接返回false
        if (cost > limit) {
            return 0;
        }

        brick_index++;
    }

    return 1;
}

int get_result(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 (is_possible(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", get_result(bricks, bricks_size));

    return 0;
}

Java算法源码

import math

class Bricks:
    def __init__(self, bricks_list):
        self.bricks = bricks_list

def calculate_cost(bricks, energy, limit):
    """
    计算在给定能量和时间限制内是否可以完成搬运。
    :param bricks: 待搬运的砖块列表
    :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 get_result(bricks):
    """
    计算在8个小时内最少需要多少能量块才能完成搬运。
    """
    bricks_obj = Bricks(bricks)
  
    # 机器人每小时只能在一个仓库干活，因此给定8小时，最多只能搬完8个仓库，如果仓库数量超过8，那么肯定干不完
    if len(bricks_obj.bricks) > 8:
        return -1

    # 每小时最多需要的能量块
    max_energy = max(bricks_obj.bricks)

    # 如果有8个仓库，那么只能1个小时干1个仓库，且机器人每小时需要能量至少是max(bricks)，这样才能保证1个小时内把最多砖块的那个仓库搬完
    if len(bricks_obj.bricks) == 8:
        return max_energy

    # 如果仓库数少于8个，那么此时每小时能量max(bricks)必然能在8小时内搬完所有仓库，但不是最优解
    ans = max_energy

    # 每小时最少需要的能量块
    min_energy = 1

    # 二分法
    while min_energy <= max_energy:
        # 取中间值
        mid = (min_energy + max_energy) >> 1

        if calculate_cost(bricks_obj.bricks, mid, 8):
            # 如果每小时充mid格能量，就能在8小时内，搬完所有砖头，则mid就是一个可能解
            ans = mid
            # 但mid不一定是最优解，因此继续尝试更小的能量块
            max_energy = mid - 1
        else:
            # 如果每小时充mid能量块，无法在8小时能完成工作，则说明每天能量块充少了，下次应该尝试充更多能量块
            min_energy = mid + 1

    return ans

# 输入获取
bricks_input = list(map(int, input("请输入砖块列表：").split()))

# 算法调用
print(get_result(bricks_input))