题解思路与方法

1. 问题分析

本题要求模拟一个工作队列的运作过程，工作队列有最大长度限制，当队列满时新任务会导致最老的任务被丢弃。执行者从1开始编号，执行者会从队列中取出任务并执行。任务执行完成的时刻由提交时刻和任务执行时间决定。

输入包括任务提交时刻和任务执行时间的序列，以及工作队列的最大长度和执行者数量。我们的目标是输出最后一个任务完成的时刻以及丢弃的任务数量。

2. 模拟过程

1. 任务队列管理：

   • 使用队列来存储任务，队列的大小不能超过最大长度。
   • 当队列满时，新任务提交会使最老的任务被丢弃，若执行者空闲且恰好有新的任务提交时，则最老任务被丢弃并立即执行新任务。

2. 执行者管理：

   • 执行者执行任务并释放出来，执行者的空闲时间决定其能接取的下一个任务。
   • 使用一个优先队列来模拟执行者的工作状态，确保优先编号的执行者优先获得任务。

3. 任务调度：

   • 当任务的提交时刻到达时，若队列未满，则直接加入队列。
   • 执行者在空闲时从队列中取最老的任务开始执行，直到任务完成。

4. 输出：

   • 输出最后一个任务完成的时刻。
   • 输出丢弃的任务数量。

3. 复杂度分析

• 时间复杂度：每个任务有最多一次入队和出队操作，因此总的时间复杂度为O(N)，其中N为任务的数量。
• 空间复杂度：需要存储任务队列和执行者的状态，空间复杂度为O(M + E)，其中M为最大队列长度，E为执行者数量。

代码实现

Python代码

from collections import deque

# 事件的定义
class Event:
    def __init__(self, time, type, exId, taskId):
        self.time = time   # 事件时间
        self.type = type   # 0: 完成事件, 1: 提交事件
        self.exId = exId   # 执行者ID, -1代表任务提交事件
        self.taskId = taskId  # 任务ID，完成事件为-1

    def __lt__(self, other):
        if self.time != other.time:
            return self.time < other.time
        if self.type != other.type:
            return self.type < other.type
        return self.exId < other.exId  # 完成事件按执行者ID排序

def simulate_work_queue(task_info, queue_limit, num_executors):
    # 任务队列最大长度，执行者数量
    tasks = [(task_info[i], task_info[i+1]) for i in range(0, len(task_info), 2)]
    N = len(tasks)
    
    # 所有任务的提交事件
    events = []
    for i, (arrive_time, exec_time) in enumerate(tasks):
        events.append(Event(arrive_time, 1, -1, i))  # type=1 表示任务提交
    
    # 按时间排序事件
    events.sort()
    
    # 空闲执行者（按ID排序）
    idle_executors = set(range(num_executors))
    
    # 等待队列，存任务ID
    task_queue = deque()
    
    discarded_count = 0
    last_finish_time = 0
    
    # 处理事件
    while events:
        event = events.pop(0)
        
        # 当前事件的时间
        current_time = event.time
        
        # 如果是任务提交事件
        if event.type == 1:
            task_id = event.taskId
            # 如果队列满了，丢弃最老的任务
            if len(task_queue) >= queue_limit:
                task_queue.popleft()
                discarded_count += 1
            # 将任务加入队列
            task_queue.append(task_id)
            
            # 尝试安排执行者执行任务
            while task_queue and idle_executors:
                # 分配任务
                executor_id = min(idle_executors)
                idle_executors.remove(executor_id)
                task_id = task_queue.popleft()
                task_arrival, task_duration = tasks[task_id]
                finish_time = current_time + task_duration
                last_finish_time = max(last_finish_time, finish_time)
                events.append(Event(finish_time, 0, executor_id, -1))  # 完成事件
                
        # 如果是任务完成事件
        elif event.type == 0:
            executor_id = event.exId
            # 执行者变为空闲
            idle_executors.add(executor_id)
            
            # 如果有任务等待，继续分配任务
            while task_queue and idle_executors:
                # 分配任务
                executor_id = min(idle_executors)
                idle_executors.remove(executor_id)
                task_id = task_queue.popleft()
                task_arrival, task_duration = tasks[task_id]
                finish_time = current_time + task_duration
                last_finish_time = max(last_finish_time, finish_time)
                events.append(Event(finish_time, 0, executor_id, -1))  # 完成事件
        
        # 按时间重新排序事件
        events.sort()

    return last_finish_time, discarded_count


# 读取输入
task_info = list(map(int, input().split()))
queue_limit, num_executors = map(int, input().split())

# 模拟并输出结果
last_finish, discarded = simulate_work_queue(task_info, queue_limit, num_executors)
print(last_finish, discarded)

Java代码

import java.util.*;

public class Main {

    static class Event implements Comparable<Event> {
        int time, type, executorId, taskId;

        Event(int time, int type, int executorId, int taskId) {
            this.time = time;
            this.type = type;
            this.executorId = executorId;
            this.taskId = taskId;
        }

        @Override
        public int compareTo(Event other) {
            if (this.time != other.time) return this.time - other.time;
            if (this.type != other.type) return this.type - other.type;
            return this.executorId - other.executorId;
        }
    }

    public static int[] simulateWorkQueue(int[] taskInfo, int queueLimit, int numExecutors) {
        int N = taskInfo.length / 2;
        int[][] tasks = new int[N][2];

        for (int i = 0; i < N; i++) {
            tasks[i][0] = taskInfo[2 * i];
            tasks[i][1] = taskInfo[2 * i + 1];
        }

        PriorityQueue<Event> eventQueue = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            eventQueue.add(new Event(tasks[i][0], 1, -1, i));
        }

        TreeSet<Integer> idleExecutors = new TreeSet<>();
        for (int i = 0; i < numExecutors; i++) {
            idleExecutors.add(i);
        }

        Queue<Integer> taskQueue = new LinkedList<>();
        int discardedCount = 0, lastFinishTime = 0;

        while (!eventQueue.isEmpty()) {
            Event event = eventQueue.poll();
            int currentTime = event.time;

            if (event.type == 0) { // Task complete
                idleExecutors.add(event.executorId);

                while (!taskQueue.isEmpty() && !idleExecutors.isEmpty()) {
                    int taskId = taskQueue.poll();
                    int finishTime = currentTime + tasks[taskId][1];
                    lastFinishTime = Math.max(lastFinishTime, finishTime);
                    eventQueue.add(new Event(finishTime, 0, idleExecutors.pollFirst(), -1));
                }
            } else { // Task arrival
                if (taskQueue.size() >= queueLimit) {
                    taskQueue.poll();
                    discardedCount++;
                }
                taskQueue.offer(event.taskId);

                while (!taskQueue.isEmpty() && !idleExecutors.isEmpty()) {
                    int executorId = idleExecutors.pollFirst();
                    int taskId = taskQueue.poll();
                    int finishTime = currentTime + tasks[taskId][1];
                    lastFinishTime = Math.max(lastFinishTime, finishTime);
                    eventQueue.add(new Event(finishTime, 0, executorId, -1));
                }
            }
        }

        return new int[]{lastFinishTime, discardedCount};
    }

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

        String[] input = scanner.nextLine().split(" ");
        int[] taskInfo = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            taskInfo[i] = Integer.parseInt(input[i]);
        }

        String[] config = scanner.nextLine().split(" ");
        int queueLimit = Integer.parseInt(config[0]);
        int numExecutors = Integer.parseInt(config[1]);

        int[] result = simulateWorkQueue(taskInfo, queueLimit, numExecutors);
        System.out.println(result[0] + " " + result[1]);

        scanner.close();
    }
}

C++代码

#include <bits/stdc++.h>
using namespace std;

struct Event {
    int time;   // 发生时间
    int type;   // 0=>执行完成, 1=>任务到达
    int exId;   // 对于完成事件表示哪个执行者, 到达事件用 -1
    int taskId; // 对应任务编号, 完成事件用 -1
};

// 自定义排序规则
bool cmp(const Event &a, const Event &b){
    if(a.time != b.time) return a.time < b.time; 
    if(a.type != b.type) return a.type < b.type;
    // 如果都是完成事件, 按执行者ID升序
    return a.exId < b.exId;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 读取第一行
    string line;
    getline(cin, line);
    vector<int> arr;
    {
        // 切分并转成int
        stringstream ss(line);
        int x;
        while(ss >> x) arr.push_back(x);
    }
    int N = arr.size() / 2;
    vector<pair<int,int>> tasks(N);
    for(int i=0; i<N; i++){
        tasks[i].first  = arr[2*i];     // arrive_time
        tasks[i].second = arr[2*i + 1]; // exec_time
    }

    // 读取第二行: M, E
    int M, E;
    cin >> M >> E;

    // 准备事件列表(先放所有到达事件)
    vector<Event> events;
    events.reserve(N*2 + 100); // 粗略开个空间
    for(int i=0; i<N; i++){
        events.push_back(Event{tasks[i].first, 1, -1, i});
    }

    // 排序(到达事件)
    sort(events.begin(), events.end(), cmp);

    // 我们需要在模拟过程中增加“执行完成事件”，
    // 因此用一个索引来遍历 + 动态插入: 可以先用list或别的结构
    // 为方便，这里演示用一个multiset来管理所有Event，边插入边弹出。
    multiset<Event, decltype(&cmp)> evq(cmp);
    for(auto &e : events) evq.insert(e);
    events.clear(); // 不再使用该vector
    
    // 等待队列(存任务ID)
    deque<int> q;
    
    // 空闲执行者(按ID升序) - 用一个有序容器，如set
    set<int> idleEx;
    for(int i=0; i<E; i++){
        idleEx.insert(i);
    }

    int discarded = 0;
    int lastFinish = 0;

    while(!evq.empty()){
        // 取最早的事件
        auto it = evq.begin();
        Event cur = *it;
        evq.erase(it);

        int timeNow = cur.time;
        int ttype   = cur.type;
        int exId    = cur.exId;
        int tId     = cur.taskId;

        if(ttype == 0){
            // 完成事件
            // exId执行者变空闲
            if(!q.empty()){
                int frontTask = q.front();
                q.pop_front();
                int finishT = timeNow + tasks[frontTask].second;
                lastFinish = max(lastFinish, finishT);
                // 插入新的完成事件
                evq.insert(Event{finishT, 0, exId, -1});
            } else {
                idleEx.insert(exId);
            }
        } else {
            // 到达事件
            if((int)q.size() == M){
                q.pop_front();
                discarded++;
            }
            q.push_back(tId);

            // 让当前空闲执行者尽可能取任务
            while(!idleEx.empty() && !q.empty()){
                int pick = *idleEx.begin();
                idleEx.erase(idleEx.begin());
                int frontTask = q.front();
                q.pop_front();
                int finishT = timeNow + tasks[frontTask].second;
                lastFinish = max(lastFinish, finishT);
                evq.insert(Event{finishT, 0, pick, -1});
            }
        }
    }

    cout << lastFinish << " " << discarded << "\n";
    return 0;
}

题目内容

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

• 提交者会在给定的时刻向工作队列提交任务，任务有执行所需的时间，执行者取出任务的时刻加上执行时间即为任务完成的时刻。
• 执行者完成任务变为空闲的时刻会从工作队列中取最老的任务执行，若这一时刻有多个空闲的执行者，其中优先级最高的会执行这个任务。编号小的执行者优先级高。初始状态下所有执行者都空闲。
• 工作队列有最大长度限制，当工作队列满而有新的任务需要加入队列时，队列中最老的任务会被丢弃。
• 特别的，在工作队列满的情况下，当执行者变为空闲的时刻和新的任务提交的时刻相同时，队列中最老的任务被取出执行，新的任务加入队列。

输入描述

输入为两行。第一行为$2N$个正整数，代表提交者提交的$N$个任务的时刻和执行时间。第一个数字是第一个任务的提交时刻，第二个数字是第一个任务的执行时间，以此类推。用例保证提交时刻不会重复，任务按提交时刻升序排列。

第二行为两个数字，分别为工作队列的最大长度和执行者的数量。

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

输出描述

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

样例1

输入

1 3 2 2 3 3
3 2

输出

7 0

样例2

输入

1 6 2 4 4 3 6 3
1 2

输出

10 0

样例3

输入

1 6 2 4 3 3 4 3 6 3
1 2

输出

10 1