题目大意

该题目要求模拟一个具有固定容量的定时器系统，根据任务的超时时刻和添加顺序，决定最终保留哪些任务，并输出最后超时任务的索引

思路

创造一个优先队列，然后枚举每一个超时任务：

1.队列的大小<n，直接进队

2.队列的大小>=n,如果新任务的超时时间小于或等于队首的超时时间，则将队首任务移除，并将新任务插入队列。 如果新任务的超时时间大于队首的超时时间，则丢弃新任务。

代码如下

cpp

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

// 定义一个足够大的数组来存储任务的超时时刻
const int MAX_TASKS = 1000005;
int timeoutTimes[MAX_TASKS]; 

int main(){
    int capacity, taskCount; // capacity表示定时器系统的容量，taskCount表示任务数量

    // 输入定时器系统容量
    cin >> capacity;

    // 输入任务数量
    cin >> taskCount;

    // 依次输入每个任务的超时时刻
    for(int i = 0; i < taskCount; i++){
        cin >> timeoutTimes[i];
    }

    // 定义一个优先队列（最大堆），存储任务的超时时刻和索引
    // 优先队列中存储的是 pair<超时时刻, 任务索引>
    priority_queue<pair<int, int>> timerQueue;

    // 遍历所有任务，按照规则将任务添加到定时器系统中
    for(int i = 0; i < taskCount; i++){
        if(timerQueue.size() < capacity){
            // 当定时器系统未满时，直接添加任务
            timerQueue.push({timeoutTimes[i], i});
        }
        else{
            // 定时器系统已满，比较新任务的超时时刻与当前系统中最晚的任务
            if(timerQueue.top().first >= timeoutTimes[i]){
                // 如果新任务的超时时刻较早或相等，则替换掉当前系统中最晚的任务
                timerQueue.pop();
                timerQueue.push({timeoutTimes[i], i});
            }
            // 否则，丢弃新任务
        }
    }

    // 由于优先队列是最大堆，队顶元素是超时时刻最大的任务
    // 若有多个任务超时刻相同，优先保留加入系统较晚的任务（即索引较大的任务）
    pair<int, int> lastTimeoutTask = timerQueue.top();

    // 输出最后超时的任务的索引号
    cout << lastTimeoutTask.second << '\n';

    return 0;
}

python

import heapq

def find_last_timeout_task(n, m, tasks):
    # 使用一个堆来维护当前系统中的任务
    # 堆中存储的是 (-t_i, -index_i)，模拟最大堆
    heap = []
    
    for index, t_i in enumerate(tasks):
        if len(heap) < n:
            heapq.heappush(heap, (-t_i, -index))
        else:
            # 获取当前堆顶的任务
            current_max_t, current_max_index = heap[0]
            current_max_t = -current_max_t
            current_max_index = -current_max_index
            if t_i > current_max_t:
                # 新任务的超时时间更大，丢弃新任务
                continue
            else:
                # 替换堆顶任务为新任务
                heapq.heappop(heap)
                heapq.heappush(heap, (-t_i, -index))
    
    # 遍历堆中的任务，找到超时时间最大的任务
    # 如果有多个任务超时时间相同，选择索引最大的任务
    max_t = -1
    max_index = -1
    for task in heap:
        t_i = -task[0]
        index = -task[1]
        if t_i > max_t or (t_i == max_t and index > max_index):
            max_t = t_i
            max_index = index
    
    return max_index

# 读取输入
if __name__ == "__main__":
    import sys
    import sys
    # 读取定时器系统容量 n
    n_line = sys.stdin.readline()
    while n_line.strip() == '':
        n_line = sys.stdin.readline()
    n = int(n_line.strip())
    
    # 读取定时任务数 m
    m_line = sys.stdin.readline()
    while m_line.strip() == '':
        m_line = sys.stdin.readline()
    m = int(m_line.strip())
    
    # 读取定时任务列表
    tasks_line = sys.stdin.readline()
    while tasks_line.strip() == '':
        tasks_line = sys.stdin.readline()
    tasks = list(map(int, tasks_line.strip().split()))
    
    # 调用函数并输出结果
    result = find_last_timeout_task(n, m, tasks)
    print(result)

java

import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Comparator;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取定时器系统容量 n
        int capacity = sc.nextInt();
        
        // 读取任务数量 m
        int taskCount = sc.nextInt();
        
        // 读取 m 个任务的超时时刻
        int[] timeoutTimes = new int[taskCount];
        for (int i = 0; i < taskCount; i++) {
            timeoutTimes[i] = sc.nextInt();
        }
        
        // 定义一个优先队列（最大堆），存储任务的超时时刻和索引
        PriorityQueue<Task> timerQueue = new PriorityQueue<>(new Comparator<Task>() {
            @Override
            public int compare(Task a, Task b) {
                if (a.timeout != b.timeout) {
                    return b.timeout - a.timeout; // 按超时时刻从大到小排序
                }
                return b.index - a.index; // 如果超时时刻相同，按索引从大到小排序
            }
        });
        
        // 遍历所有任务，按照规则将任务添加到定时器系统中
        for (int i = 0; i < taskCount; i++) {
            int timeout = timeoutTimes[i];
            if (timerQueue.size() < capacity) {
                // 当定时器系统未满时，直接添加任务
                timerQueue.offer(new Task(timeout, i));
            } else {
                // 定时器系统已满，比较当前任务的超时时刻与队首任务
                Task currentMaxTask = timerQueue.peek();
                if (currentMaxTask.timeout >= timeout) {
                    // 如果当前任务的超时时刻较小或相等，替换掉队首任务
                    timerQueue.poll();
                    timerQueue.offer(new Task(timeout, i));
                }
            }
        }
        
        // 队首元素即为系统中超时时间最大的任务
        Task lastTimeoutTask = timerQueue.peek();
        
        // 输出最后超时任务的索引号
        System.out.println(lastTimeoutTask.index);
        
        sc.close();
    }
}

// 定义一个任务类，包含超时时刻和索引
class Task {
    int timeout;
    int index;
    
    Task(int timeout, int index) {
        this.timeout = timeout;
        this.index = index;
    }
}