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

【华为上机真题 2022】流水线

news 来源：原创 2024/5/20 5:16:34

🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 关注专栏： 数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬

一、题目描述

1.1 输入描述

1.2 输出描述

1.3 测试样例

1.3.1 示例 1

二、解题思路

三、代码实现

四、时间复杂度

一、题目描述

工厂有 m 条流水线，用于并行完成 n 个独立的作业，工厂设置了一个调度系统，在安排作业时，总是优先执行处理时间最短的作业。

现给定流水线个数 m，和需要完成的作业数 n，每个作业的处理时间分别为 t1、t2、...、tn。请编程计算处理完成所有作业的耗时为多少？

当 n > m 时，首先处理时间短的 m 个作业进入流水线，其他的等待，当某个作业完成时，依次从剩余作业中取处理时间最短的进入处理。

1.1 输入描述

第一行为 2 个整数（采用空格分隔），分别表示流水线个数 m 和作业数 n。

第二行输入 n 个整数（采用空格分隔），表示每个作业的处理时长 t1、t2、...、tn。

其中，0 < m,n < 100, 0 < t1,t2,...,tn < 100。

注：输入都是合法的。

1.2 输出描述

输出处理完所有作业的总时长。

1.3 测试样例

1.3.1 示例 1

输入

3 5
8 4 3 2 10

输出

说明：先安排时间为 2、3、4 的三个作业。

第一条流水线先完成作业，然后调度剩余时间最短的作业 8；

第二条流水线完成作业，然后调度剩余时间最短的作业 10；

总耗时就是第二条流水线完成作业的时间 13（3+10）；

提示：每次将时间最短的那个任务，扔进当前有空的流水线里面处理。注意这个不是最优的调度方案。

二、解题思路

本题比较简单，主要是模拟流水线处理作业的流程，优先处理短作业。

先将所有作业排序，因为需要优先处理短作业。然后可以分两种情况处理：

（1）如果 m >= n，说明流水线个数大于作业的个数，每个作业可以分配到一个流水线上去，作业时间最长的处理完成后，所有作业都会处理完。所以最长时间即为需要时间最长的那个作业。

（2）如果 m < n，说明流水线个数小于作业的个数，需要按照每批次 m 个作业进行处理，根据作业的时间从短到长处理。这里假设 dp[ i ] 表示处理前 i 个作业需要的时间，那么，有如下动态方程：

dp[i] = dp[i] + dp[i - m];  i >= m

上述公式表示处理前 i 个作业的时间为当前 i 作业的时间加上 dp[i - m] 需要的时间，因为有 m 个流水线，第 i 个作业一定放置在 i - m 个作业的流水线上。

三、代码实现

代码实现如下所示。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n, m;
    while (cin>>m>>n) {
        int val;
        vector<int>g;
        for (int i = 0; i < n; ++i) {
            cin>>val;
            g.push_back(val);
        }
        sort(g.begin(), g.end());
        if (m >= n) {
            cout<<g[n - 1]<<endl;
            continue;
        }

        for (int i = m; i < n; ++i) {
            g[i] = g[i] + g[i - m];
        }

        cout<<g[n - 1]<<endl;
    }
    return 0;
}