题目部分

解读与分析

题目解读：

把所有的作业按照从小到的顺序排序，依次放到流水线中。当某个流水线完成，从作业的队列中拿出下一个，放到流水线中。求最终所有作业完成的时间。

分析与思路：

此题先对作业从小到大排序。
当流水线数大于作业数，则输入作业中最大的值。
当流水线数小于作业数，
1. 设作业时间为 sum，初始值为 0。将排序好的作业依次放到流水线中。
2. 计算流水线中最小值，设为 min，赋值 sum += min，并把流水中的所有作业都减去 min，然后把下一个作业放到值为 0 流水线中，循环，直到最后一个作业放到流水线中。
3. 最后一次的时间为流水线中的最大值(设为max)，并 sum += max。输出 sum。

时间复杂度和空间复杂度均为 O(n)。

代码实现

Java代码

import java.util.Arrays;
import java.util.Scanner;/*** 流水线* * @since 2023.10.25* @version 0.1* @author Frank**/
public class Pipeline {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {String input = sc.nextLine();String[] inputStr = input.split(" ");int m = Integer.parseInt(inputStr[0]);int n = Integer.parseInt(inputStr[1]);int[] workInfo = new int[n];input = sc.nextLine();inputStr = input.split(" ");for (int i = 0; i < n; i++) {workInfo[i] = Integer.parseInt(inputStr[i]);}processPipeline(m, n, workInfo);}}private static void processPipeline(int m, int n, int[] workInfo) {Arrays.sort(workInfo);if (m >= n) {System.out.println(workInfo[n - 1]);return;}int[] pipeline = new int[m];int sum = workInfo[0];int minIndex = 0;int Value2Minus = workInfo[0];for (int i = 0; i < m; i++) {pipeline[i] = workInfo[i] - Value2Minus;}int workIndex = m;while (workIndex <= n - 1) {pipeline[minIndex] = workInfo[workIndex];if (workIndex == n - 1) {sum += pipeline[getMaxPipepline(pipeline)];break;} else {minIndex = getMinPipepline(pipeline);Value2Minus = pipeline[minIndex];sum += Value2Minus;for (int i = 0; i < m; i++) {pipeline[i] -= Value2Minus;}}workIndex++;}System.out.println(sum);}private static int getMinPipepline(int[] pipeline) {int index = 0;int min = pipeline[0];for (int i = 0; i < pipeline.length; i++) {if (pipeline[i] < min) {index = i;min = pipeline[i];}}return index;}private static int getMaxPipepline(int[] pipeline) {int index = 0;int max = pipeline[0];for (int i = 0; i < pipeline.length; i++) {if (pipeline[i] > max) {index = i;max = pipeline[i];}}return index;}
}

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {while (line = await readline()) {var inputArr = line.split(" ");var m = parseInt(inputArr[0]);var n = parseInt(inputArr[1]);var workInfo = new Array();line = await readline();var inputStr = line.split(" ");for (var i = 0; i < n; i++) {workInfo[i] = parseInt(inputStr[i]);}processPipeline(m, n, workInfo);}
}();function processPipeline(m, n, workInfo) {workInfo.sort(function compareFn(a, b) {return a - b;});console.log( workInfo );if (m >= n) {console.log(workInfo[n - 1]);return;}var pipeline = new Array();var sum = workInfo[0];var minIndex = 0;var value2Minus = workInfo[0];for (var i = 0; i < m; i++) {pipeline[i] = workInfo[i] - value2Minus;}console.log( pipeline );var workIndex = m;while (workIndex <= n - 1) {pipeline[minIndex] = workInfo[workIndex];if (workIndex == n - 1) {sum += pipeline[getMaxPipepline(pipeline)];break;} else {minIndex = getMinPipepline(pipeline);value2Minus = pipeline[minIndex];sum += value2Minus;for (var i = 0; i < m; i++) {pipeline[i] -= value2Minus;}console.log( pipeline );}workIndex++;}console.log(sum);
}function getMinPipepline(pipeline) {var index = 0;var min = pipeline[0];for (var i = 0; i < pipeline.length; i++) {if (pipeline[i] < min) {index = i;min = pipeline[i];}}return index;
}function getMaxPipepline(pipeline) {var index = 0;var max = pipeline[0];for (var i = 0; i < pipeline.length; i++) {if (pipeline[i] > max) {index = i;max = pipeline[i];}}return index;
}

(完)