题目大意

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

思路

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

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;
    }
}

题目内容

有这样一个定时器系统:

$(1)$该系统精度为$1$刻度、可容纳$n$个超时任务(即容量为$n$);

$(2)$每个任务里包含该任务超时时刻$t$(当系统时钟到达t时，该任务开始执行)，$t$为正整数;

$(3)$同一时刻超时的任务按照加入系统的先后顺序依次执行超时任务;

$(4)$当定时器系统中任务数不足$n$个时，可直接添加定时任务;

$(5)$当定时器系统中任务数达到$n$个时，假定待添加任务的超时时刻为$ti$，系统中最后执行的任务的超时时刻为$tj$;

如果$ti > tj$,丢弃待添加的任务;否则丢弃系统中最晚执行的超时任务，并将待添加任务加入系统中。

现给定该定时器系统容量$n$，短时内(不到$1$刻度)依次向该定时器系统添加$m$个定时任务$tasks$，假定当前时钟为$0$时刻，即向该定时器系统添加的任务都是尚未超时的任务。

请输出该定时器系统中最后超时的任务索引号，其中索引号是指:当前$task$在$tasks$中的下标(下标从$0$开始计);如果多个任务同时超时，请输出最大的索引号。

输入描述

第一行:定时器系统容量$n;1<=n<=10^3$

第二行:定时任务数$m;1<= m<=10^6$

第三行:定时任务列表内容$tasks$，每个数据通过空格隔开;$1<= tasks[i]<=10^5$。

输出描述

输出最后超时的任务索引号

样例1

输入

2
12
1 2 3 4 6 19 20 21 22 23 25 1

输出

11

说明

定时器系统容量为$2$，最多容纳$2$个定时任务，因此最终定时器里只会存在两个任务:

分别是$1$(索引号$0$)、$1$(索引号$11$)，这两个任务同时超时，题目要求返回更大的索引，因此返回$11$

样例2

输入

1
2
10 2

输出

1 

说明

定时器系统容量为$1$，最多容纳$1$个定时任务，因此最终定时器里只会存在$1$个任务:

$2$:

$2$对应索引号为$1$,因此返回$1$

样例3

输入

20
5
1 2 3 4 5

输出

4

说明

定时器系统容量为$20$，最多容纳$20$个定时任务，而添加的任务数为$5$，没有超过定时器系统规格，因此最终定时器里会存在以下任务:$1\ 2\ 3\ 4\ 5$;

$5$最晚超时，因此返回$5$对应的下标$4$