P2270.第1题-最后超时的定时任务索引号

1000ms

Tried: 831

Accepted: 178

Difficulty: 3

所属公司 : 华为

算法与标签>模拟

题目内容

有这样一个定时器系统:

$(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

输出

说明

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

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

样例2

输入

1
2
10 2

输出

说明

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

$2$ :

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

样例3

输入

20
5
1 2 3 4 5

输出

说明

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

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

输入

预期输出（选填）

题目大意

思路

P2270.第1题-最后超时的定时任务索引号

题目内容

输入描述

输出描述

样例1

样例2

样例3

Status

Development

Support

About