华为OD机考双机位C卷 - 流水线（Java Python JS C/C++ GO ）

最新华为OD机试

真题目录：点击查看目录

华为OD面试真题精选：点击立即查看

华为OD机考双机位C卷

题目描述

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

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

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

输入描述

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

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

0< m,n<100，0<t1,t2…tn<100。

注：保证输入都是合法的。

输出描述

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

示例1

输入

3 5 8 4 3 2 10

输出

13

说明

1、先安排时间为2、3、4的3个作业。
2、第一条流水线先完成作业，然后调度剩余时间最短的作业8。
3、第二条流水线完成作业，然后调度剩余时间最短的作业10。
4、总工耗时就是第二条流水线完成作业的时间13（3+10）。

解题思路

作业分配：

• 如果作业数n小于等于流水线数m，则每个作业直接分配给一条流水线，处理完的总时间就是所有作业的处理时间。

• 如果作业数n大于流水线数m，则优先将处理时间最短的m个作业分配给各条流水线。

• 对于剩下的作业，依次从处理时间最短的作业中选择，并将其分配到当前处理时间最短的流水线上。每分配一个作业，就将该流水线的总时间更新。

以示例输入为例，3条流水线，5个作业，处理时间为 [8, 4, 3, 2, 10]：

1. 排序后的作业时间：[2, 3, 4, 8, 10]
2. 分配前3个作业给流水线：
   • 流水线1：处理时间 2
   • 流水线2：处理时间 3
   • 流水线3：处理时间 4
3. 作业完成情况：
   • 流水线1完成（时间2），进入下一个作业8（更新为10）。
   • 流水线2完成（时间3），进入下一个作业10（更新为13）。
4. 最后计算所有流水线上时间的最大值，输出13。

Java

importjava.util.Arrays;importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);// 输入流水线个数m和作业数nintnum_of_pipelines=scanner.nextInt();intnum_of_jobs=scanner.nextInt();// 输入每个作业的处理时长t1,t2...tnint[]job_times=newint[num_of_jobs];for(inti=0;i<num_of_jobs;i++){job_times[i]=scanner.nextInt();}// 对作业处理时长进行排序Arrays.sort(job_times);// 创建一个长度为流水线个数的数组，用于存储每条流水线的总时长int[]total_time=newint[num_of_pipelines];// 如果作业数小于等于流水线个数，直接将作业分配到每条流水线上if(num_of_jobs<=num_of_pipelines){total_time=job_times;}else{// 将处理时长最短的m个作业分配到每条流水线上total_time=Arrays.copyOfRange(job_times,0,num_of_pipelines);// 处理剩余的作业for(inti=num_of_pipelines;i<num_of_jobs;i++){intmin_time=Integer.MAX_VALUE;intindex=-1;// 找到处理时长最短的流水线for(intj=0;j<num_of_pipelines;j++){if(total_time[j]<min_time){min_time=total_time[j];index=j;}}// 将作业分配到处理时长最短的流水线上total_time[index]+=job_times[i];}}// 找到处理时长最长的流水线intmax_time=Integer.MIN_VALUE;for(inti=0;i<num_of_pipelines;i++){if(total_time[i]>max_time){max_time=total_time[i];}}// 输出处理完所有作业的总时长System.out.println(max_time);}}

Python

num_of_pipelines,num_of_jobs=map(int,input().split())# 流水线个数，作业数job_times=list(map(int,input().split()))# 每个作业的处理时间job_times.sort()# 按处理时间从小到大排序total_time=[]# 记录每个流水线的总耗时ifnum_of_jobs<=num_of_pipelines:# 如果作业数小于等于流水线个数total_time=job_times# 每个作业都分配到一个流水线else:total_time=job_times[:num_of_pipelines]# 先将处理时间最短的m个作业分配到流水线foriinrange(num_of_pipelines,num_of_jobs):# 处理剩余的作业min_time=min(total_time)# 找到当前总耗时最小的流水线index=total_time.index(min_time)# 找到最小耗时的流水线的索引total_time[index]+=job_times[i]# 将当前作业分配到最小耗时的流水线print(max(total_time))# 输出处理完所有作业的总耗时

JavaScript

constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});letm,n;lettimes=[];rl.on('line',(line)=>{if(!m&&!n){[m,n]=line.trim().split(' ').map(Number);}elseif(times.length<n){times.push(...line.trim().split(' ').map(Number));}if(m&&n&&times.length===n){rl.close();constnum_of_pipelines=m;constnum_of_jobs=n;constjob_times=times;job_times.sort((a,b)=>a-b);lettotal_time=newArray(num_of_pipelines).fill(0);if(num_of_jobs<=num_of_pipelines){total_time=job_times;}else{total_time=job_times.slice(0,num_of_pipelines);for(leti=num_of_pipelines;i<num_of_jobs;i++){letmin_time=Infinity;letindex=-1;for(letj=0;j<num_of_pipelines;j++){if(total_time[j]<min_time){min_time=total_time[j];index=j;}}total_time[index]+=job_times[i];}}letmax_time=-Infinity;for(leti=0;i<num_of_pipelines;i++){if(total_time[i]>max_time){max_time=total_time[i];}}console.log(max_time);}});

C++

#include<iostream>#include<vector>#include<algorithm>using namespace std;intmain(){intnum_of_pipelines,num_of_jobs;cin>>num_of_pipelines>>num_of_jobs;vector<int>job_times(num_of_jobs);for(inti=0;i<num_of_jobs;i++){cin>>job_times[i];}sort(job_times.begin(),job_times.end());vector<int>total_time(num_of_pipelines);if(num_of_jobs<=num_of_pipelines){total_time=job_times;}else{total_time.assign(job_times.begin(),job_times.begin()+num_of_pipelines);for(inti=num_of_pipelines;i<num_of_jobs;i++){intmin_time=*min_element(total_time.begin(),total_time.end());intindex=distance(total_time.begin(),find(total_time.begin(),total_time.end(),min_time));total_time[index]+=job_times[i];}}cout<<*max_element(total_time.begin(),total_time.end())<<endl;return0;}

Go

packagemainimport("fmt""math""sort")funcmain(){varnumOfPipelines,numOfJobsint// 输入流水线个数m和作业数nfmt.Scan(&numOfPipelines,&numOfJobs)// 输入每个作业的处理时长t1,t2...tnjobTimes:=make([]int,numOfJobs)fori:=0;i<numOfJobs;i++{fmt.Scan(&jobTimes[i])}// 对作业处理时长进行排序sort.Ints(jobTimes)// 创建一个长度为流水线个数的数组，用于存储每条流水线的总时长totalTime:=make([]int,numOfPipelines)// 如果作业数小于等于流水线个数，直接将作业分配到每条流水线上ifnumOfJobs<=numOfPipelines{copy(totalTime,jobTimes)// 补齐剩余的流水线时间为0fori:=numOfJobs;i<numOfPipelines;i++{totalTime[i]=0}}else{// 将处理时长最短的m个作业分配到每条流水线上copy(totalTime,jobTimes[:numOfPipelines])// 处理剩余的作业fori:=numOfPipelines;i<numOfJobs;i++{minTime:=math.MaxInt32 index:=-1// 找到处理时长最短的流水线forj:=0;j<numOfPipelines;j++{iftotalTime[j]<minTime{minTime=totalTime[j]index=j}}// 将作业分配到处理时长最短的流水线上totalTime[index]+=jobTimes[i]}}// 找到处理时长最长的流水线maxTime:=math.MinInt32fori:=0;i<numOfPipelines;i++{iftotalTime[i]>maxTime{maxTime=totalTime[i]}}// 输出处理完所有作业的总时长fmt.Println(maxTime)}

C语言

#include<stdio.h>#include<stdlib.h>intcompare(constvoid*a,constvoid*b){return(*(int*)a-*(int*)b);}intmain(){intnum_of_pipelines,num_of_jobs;scanf("%d %d",&num_of_pipelines,&num_of_jobs);int*job_times=(int*)malloc(num_of_jobs*sizeof(int));for(inti=0;i<num_of_jobs;i++){scanf("%d",&job_times[i]);}qsort(job_times,num_of_jobs,sizeof(int),compare);int*total_time=(int*)malloc(num_of_pipelines*sizeof(int));for(inti=0;i<num_of_pipelines;i++){total_time[i]=(i<num_of_jobs)?job_times[i]:0;}if(num_of_jobs>num_of_pipelines){for(inti=num_of_pipelines;i<num_of_jobs;i++){intmin_time=total_time[0];intindex=0;for(intj=1;j<num_of_pipelines;j++){if(total_time[j]<min_time){min_time=total_time[j];index=j;}}total_time[index]+=job_times[i];}}intmax_time=total_time[0];for(inti=1;i<num_of_pipelines;i++){if(total_time[i]>max_time){max_time=total_time[i];}}printf("%d\n",max_time);free(job_times);free(total_time);return0;}

完整用例

用例1

3 5 8 4 3 2 10

用例2

2 4 5 6 7 8

用例3

4 6 1 2 3 4 5 6

用例4

1 3 10 20 30

用例5

5 5 1 2 3 4 5

用例6

10 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

用例7

6 10 10 9 8 7 6 5 4 3 2 1

用例8

7 8 1 2 3 4 5 6 7 8

用例9

4 15 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75

用例10

8 12 2 4 6 8 10 12 14 16 18 20 22 24