手撕算法-严刑拷打
题目背景：
给定 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;
}
原文地址：https://blog.csdn.net/myprogramc/article/details/144772147
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！