华为OD机考题目《流水线》100分题目

前几天有个小伙伴在牛客私信我，说想了解一下“流水线” 这道题的思路和解法。

我在****上找到了这道题，链接：https://blog.****.net/qq_41772375/article/details/125075726

链接中的第三题就是“流水线”。

如果你打不开上面链接，看这个截图也行。

读了一下题目，了解到题目大意是，有 m个流水线， n个作业，每个作业有一个执行耗时，每个流水线每次都优先执行耗时最短的那个作业。问你，所有作业都搞完，需要多长时间。

首先，这是一道简单题，100分吧应该。

题目给出的输入是：

m 空格 n 回车

耗时空格耗时空格耗时 .... 耗时

m n
耗时1 耗时2 耗时3 ... 耗时n

那么对于这个输入，我们首先考虑一下接收它的代码：

m是一个独立的数字，后面要用。 n代表了下一行数字的个数。

用c++代码：

//m个流水线，n个作业
int m, n;
cin >> m >> n;
vector<int> rVec;
while (n)
{
    n--;
  int tn;
  cin >> tn;
  rVec.push_back(tn);
}

输入接收完了，我们注意到题目是按照耗时短的优先处理，所以我们先排个序：

sort(rVec.begin(), rVec.end());

此处利用c++提供的 sort函数即可，有小到大排序。

接下来我们要怎么安排作业呢？

当作业数小于等于流水线数的时候，我们给每个流水线分配一个作业即可，那么耗时最长的那个作业，就是总时长了。

当作业数大于流水线数的时候，我们就要给某些流水线分配多个作业了。

为了便于理解如何分配，这里我画了一个图来表达：

假设我们有8个作业，3个流水线。

那么首先按顺序给3个流水线分配耗时最短的三个任务：

接下来，第四个任务要怎么安排，才能使总耗时最短呢？答案显而易见，就是安排给流水线1，因为它能第一个完成目前已分配的作业。

以此类推，只要我们先把任务按照从小到大排序，然后每次都把任务安排给当前最闲的那个流水线，就OK了。

那么，怎么才能快速找到哪个流水线最闲呢？

办法有很多，我来出一个最笨的。

我创建一个vector<int>，里面保存了每个流水线当前已分配的工作会占用的时长，初始默认是0.

然后每分配一个任务，都重新排序一下，让最闲的排到第一位。

然后再安排任务给第一个流水线，就能保证第一个永远是最闲的那个了。

如下图，当我要分配第5个任务前，我先把流水线排个序，显而易见流水线1排到了最后了。

所以作业5会分配给流水线2 。

就这样，在所有作业分配完之后，别忘了最后一次排序。

排完之后，取最后一个的大小，就是最长时长了。

接下来上代码：

 vector<int> flow(m,0);
for (auto x : rVec)
{
    flow[0] += x;
    sort(flow.begin(), flow.end());
}
cout << flow.back() << endl;

前面有提到，如果流水线个数大于等于作业个数，则直接丢出最大的那个作业即可。

于是，整体代码如下：

#include <string>
#include <iostream>
#include <stdlib.h>
#include <map>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

//注意：请勿直接抄袭，否则会被判定作弊，等于没考。
int main() {
    //m个流水线，n个作业
    int m, n;
    cin >> m >> n;
    vector<int> rVec;
    while (n)
    {
        n--;
        int tn;
        cin >> tn;
        rVec.push_back(tn);
    }
    sort(rVec.begin(), rVec.end());
    if (m>= rVec.size())
    {
        cout << rVec.back() << endl;
        return 0;
    }

    vector<int> flow(m,0);
    for (auto x : rVec)
    {
        flow[0] += x;
        sort(flow.begin(), flow.end());
    }
    cout << flow.back() << endl;
    return 0;
}

那么，聪明的你，还有什么其他思路呢？欢迎留言讨论。