当前位置：首页 > article >正文

手撕算法-严刑拷打

article 2025/1/6 4:40:58

题目背景：

给定 m 台“相同”机器（或工作线程、工人等），以及 n 个“任务”或“工作”，每个任务都有一个执行时间。我们需要将这 n 个任务分配到这 m 台机器上，使得所有任务都执行完所需的总时间（完工时间）最小，即要找出一个最优的分配方案，让“最后一台机器”完成任务的时间尽可能早。

解释：

•	有 m 台并行机器。
•	有 n 个任务，每个任务的执行时间分别是 w\_water[0], w\_water[1], \dots, w\_water[n-1]。
•	每台机器可顺序执行若干个任务，但同一个任务不能拆分、不能并行执行。
•	分配完成后，以所有机器中“完成时间最晚”的那台机器的时刻作为本次调度的“完工时间”。
•	要求输出最优分配下的“最小完工时间”。

题目要求：

1.	输入
•	第一行包含两个整数 m, n，分别表示机器数量和任务数量。
•	接下来 n 行（或合并为一行，代码里只是 for i in range(n) 读入），每行一个整数，表示该任务所需执行时间。
2.	输出
•	一个整数，表示任务在 m 台机器上全部执行完毕所需的最短时间（即最小化的“最大完工时间”）。

示例：

•	输入：
3 6
4 5 7 8 2 3

•	输出：
12

代码思路与解释

代码采用贪心 + 最小堆的思路：

1.	初始化最小堆
•	先将前 m 个任务（如果任务数 \ge m）分别分配给 m 台机器，放入一个“小根堆”（std::priority_queue<int, std::vector<int>, std::greater<int>>）。
•	堆顶（minTime.top()) 表示“当前机器所累积的执行时间”最少的那台机器。
2.	分配后续任务
•	对于剩余的任务（第 m 个及之后的），取出堆顶的那台机器时间 top，给它分配下一个任务的执行时间，然后再将更新后的总时间推回堆中。
•	这样做保证每次都将新的任务分配给当前最空闲（或时间最短）的机器，在局部层面上看是一种贪心最优。
3.	计算结果
•	最终堆中存的就是 m 台机器各自的“总执行时间”。我们只要找出其中的最大值，就是所有任务完成的完工时间。
•	代码里通过 while (!minTime.empty()) { time = max(time, minTime.top()); minTime.pop(); } 获取堆中最大的时间。

时间复杂度：

•	构建堆为 O(m)（通常可以视为 O(\min(m,n))）。
•	遍历后续 n - m 个任务时，每次取堆顶 + 插入堆都要 O(\log m)。
•	综合起来是 O(n \log m)，适用于 n 远大于 m 的场景。

代码：

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm> // for max

int water(int m, const std::vector<int>& w_water) {
    int time = 0;
    std::priority_queue<int, std::vector<int>, std::greater<int> > minTime;

    // 分配前 m 个任务
    for (int i = 0; i < m && i < w_water.size(); i++) {
        minTime.push(w_water[i]);
    }

    // 分配剩余任务
    for (int i = m; i < w_water.size(); i++) {
        int top = minTime.top();
        minTime.pop();
        top += w_water[i];a
        minTime.push(top);
    }

    // 找出最大完成时间
    while (!minTime.empty()) {
        time = std::max(time, minTime.top());
        minTime.pop();
    }

    return time;
}

int main() {
    int m, n;
    std::vector<int> w_water;

    // 输入机器数量和任务数量
    std::cin >> m >> n;

    // 输入任务时间
    for (int i = 0; i < n; i++) {
        int tmp;
        std::cin >> tmp;
        w_water.push_back(tmp);
    }

    // 计算结果并输出
    int result = water(m, w_water);
    std::cout << result << std::endl;

    return 0;
}