Mdr-C-Tutorial

主题

30402：最短生产时间 ​

题目 ​

给定每台机器生产一件产品所需的时间，求生产至少 target 件产品的最短时间。

解析 ​

时间越长，累计产量只会增加，因此可对答案进行二分。不能用某一台机器的耗时乘以目标数量构造上界；这里从 1 开始倍增，直到找到可行时间，倍增和 UINT64_MAX 都单独处理。

在可行性判断中计算 time / machine_times[i]，一旦累计数量达到目标就立即返回，避免总产量相加溢出。

答案 ​

c
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

static bool can_produce(
    const uint64_t *machine_times,
    size_t machine_count,
    uint64_t time,
    uint64_t target
) {
    uint64_t produced = 0;
    for (size_t i = 0; i < machine_count; ++i) {
        uint64_t amount = time / machine_times[i];
        if (amount >= target - produced) {
            return true;
        }
        produced += amount;
    }
    return produced >= target;
}

bool minimum_production_time(
    const uint64_t *machine_times,
    size_t machine_count,
    uint64_t target,
    uint64_t *out_time
) {
    if (out_time == NULL) {
        return false;
    }
    if (target == 0) {
        *out_time = 0;
        return true;
    }
    if (machine_count == 0 || machine_times == NULL) {
        return false;
    }
    for (size_t i = 0; i < machine_count; ++i) {
        if (machine_times[i] == 0) {
            return false;
        }
    }

    uint64_t high = 1;
    while (!can_produce(
        machine_times, machine_count, high, target
    )) {
        if (high == UINT64_MAX) {
            return false;
        }
        high = high > UINT64_MAX / 2
            ? UINT64_MAX
            : high * 2;
    }

    uint64_t low = 0;
    while (low < high) {
        uint64_t middle = low + (high - low) / 2;
        if (can_produce(
            machine_times, machine_count, middle, target
        )) {
            high = middle;
        } else {
            low = middle + 1;
        }
    }
    *out_time = low;
    return true;
}

倍增寻找上界和答案二分都只调用线性可行性判断，时间复杂度为 O(mlog⁡T)，额外空间为 O(1)。