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

模拟工作队列 - 华为OD机试真题(JavaScript卷)

news 2025/6/30 7:15:18

华为OD机试题库《C++》限时优惠 9.9

华为OD机试题库《Python》限时优惠 9.9

华为OD机试题库《JavaScript》限时优惠 9.9

针对刷题难，效率慢，我们提供一对一算法辅导，针对个人情况定制化的提高计划（全称1V1效率更高）。

看不懂有疑问需要答疑辅导欢迎私VX： code5bug

题目描述

让我们来模拟一个工作队列的运作，有一个任务提交者和若干任务执行者，执行者从1开始编号。

提交者会在给定的时刻向工作队列提交任务，任务有执行所需的时间，执行者取出任务的时刻加上执行时间即为任务完成的时刻，执行者完成任务变为空闲的时刻会从工作队列中取最老的任务执行，若这一时刻有多个空闲的执行者，其中优先级最高的会执行这个任务。编号小的执行者优先级高，初始状态下所有执行者都空闲。

工作队列有最大长度限制，当工作队列满有新的任务加入队列时，队列中最老的任务会被丢弃。

在工作队列满的情况下，当执行者变为空闲的时刻和新的任务提交的时刻相同时，队列中最老的任务被取出执行，新的任务加入队列。

输入描述

输入为两行。

第一行为 2N 个正整数，代表提交者提交的N个任务的时刻和执行时间。第一个数字是第一个任务的提交时刻，第二个数字是第一个任务的执行时间，以此类推。用例保证提交时刻不会重复，任务按提交时刻升序排列。
第二行为两个数字，分别为工作队列的最大长度和执行者的数量。

两行的数字都由空格分割。N不超过20，数字为不超过1000的正整数。

输出描述

输出两个数字，分别为最后一个任务执行完成的时刻和被丢弃的任务的数量，数字由空格分隔。

示例1

输入：

1 3 2 2 3 3
3 2

输出：

7 0

说明：

两个执行者，队列最大长度3，所有任务均能正常加入并执行，无任务丢弃。

示例2

输入：

1 6 2 4 4 3 6 3
1 2

输出：

10 0

说明：

队列最大长度1较小，但任务提交和执行顺序使得没有任务丢弃。

题解

这道题目属于模拟题，主要考察对工作队列和任务调度过程的模拟能力。需要按照特定的规则处理任务的提交、执行和丢弃，同时跟踪执行者的状态和工作队列的变化。

解题思路

任务提交与队列管理：提交者在特定时刻提交任务，如果队列已满，则丢弃最老的任务。任务按提交时间升序处理。
任务执行：执行者在空闲时从队列中取出最老的任务执行。如果有多个空闲执行者，编号小的优先执行。
时间模拟：通过时间循环模拟任务的提交和执行过程，每次时间步进检查是否有任务完成，并处理新提交的任务。
状态跟踪：使用优先队列（最小堆）跟踪执行者的任务完成时间，使用双端队列管理等待执行的任务队列。

JavaScript

const rl = require('readline').createInterface({input: process.stdin,output: process.stdout,
});var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;(async () => {// 读取输入数据const arr = (await readline()).split(' ').map(Number); // 将输入字符串转换为数字数组const [queue_length, executors] = (await readline()).split(' ').map(Number); // 读取队列长度和执行者数量let last_finish_time = 0; // 最后一个任务完成时间let discard_task = 0;     // 被丢弃的任务数量const runner_task = [];   // 正在执行的任务堆（存储任务完成时间）const todo_queue = [];    // 等待执行的任务队列（存储任务执行时间）// 执行任务函数function execute_task(now_time) {// 处理已完成的任务（从堆顶移除）while (runner_task.length > 0 && runner_task[0] <= now_time) {runner_task.shift();}// 如果有空闲执行者，从队列中取任务执行while (runner_task.length < executors && todo_queue.length > 0) {const duration = todo_queue.shift(); // 获取任务执行时间const finish_time = now_time + duration; // 计算完成时间last_finish_time = Math.max(last_finish_time, finish_time); // 更新最后完成时间// 将任务加入堆（模拟最小堆）runner_task.push(finish_time);runner_task.sort((a, b) => a - b); // 排序以维持堆性质}}let i = 0; // 任务提交索引for (let now = 0; ; now++) { // 模拟时间流逝execute_task(now); // 执行当前时间的任务// 处理当前时间提交的任务while (i < arr.length && arr[i] <= now) {if (todo_queue.length === queue_length) {todo_queue.shift(); // 队列已满，丢弃最老的任务discard_task++;}todo_queue.push(arr[i + 1]); // 将任务加入队列i += 2; // 移动到下一个任务提交时间execute_task(now); // 立即尝试执行新任务}// 检查是否所有任务都已完成if (runner_task.length === 0 && todo_queue.length === 0 && i >= arr.length) {break; // 终止时间循环}}// 输出结果console.log(last_finish_time, discard_task);rl.close();
})();