(B卷,100分)- 流水线（Java & JS & Python & 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。

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

输出描述

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

用例

题目解析

简单的逻辑题。解题思路如下：

题目说“总是优先执行处理时间最短的作业”，因此我们可以将8 4 3 2 10 进行升序排序变为2 3 4 8 10，然后依次将排序后元素投入对应流水线中，如下图所示

 计算每条流水线的时间总和，最大的个就是题解。

Java算法源码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int m = sc.nextInt();
    int n = sc.nextInt();

    int[] times = new int[n];
    for (int i = 0; i < n; i++) times[i] = sc.nextInt();

    System.out.println(getResult(m, n, times));
  }

  public static int getResult(int m, int n, int[] times) {
    Arrays.sort(times);

    int[] mArr = new int[m];
    for (int i = 0; i < n; i++) {
      mArr[i % m] += times[i];
    }

    return Arrays.stream(mArr).max().orElse(0);
  }
}

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 2) {
    let [m, n] = lines[0].split(" ").map((ele) => parseInt(ele));
    let times = lines[1]
      .split(" ")
      .slice(0, n)
      .map((ele) => parseInt(ele));

    times.sort((a, b) => a - b);

    let mArr = new Array(m).fill(0);

    times.forEach((time, idx) => {
      mArr[idx % m] += time;
    });

    console.log(Math.max(...mArr));

    lines.length = 0;
  }
});

Python算法源码

# 输入获取
m, n = map(int, input().split())
times = list(map(int, input().split()))


# 算法入口
def getResult():
    times.sort()

    mArr = [0]*m

    for i in range(len(times)):
        mArr[i % m] += times[i]

    return max(mArr)


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>
#include <stdlib.h>

#define MAX(a,b) ((a) > (b) ? (a) : (b))

int cmp(const void* a, const void* b) {
    return (*(int*) a) - (*(int*) b);
}

int main() {
    int m, n;
    scanf("%d %d", &m, &n);

    int times[n];
    for(int i=0; i<n; i++) {
        scanf("%d", &times[i]);
    }

    qsort(times, n, sizeof(int), cmp);

    int* mArr = (int*) calloc(m, sizeof(int));
    for(int i=0; i<n; i++) {
        mArr[i % m] += times[i];
    }

    int ans = mArr[0];
    for(int i=1; i<m; i++) {
        ans = MAX(ans, mArr[i]);
    }

    printf("%dn", ans);

    return 0;
}