蓝桥杯2022年第八届javaB组第七题：外卖店优先级

第七题：外卖店优先级
题目描述

“饱了么”外卖系统中维护着 N 家外卖店，编号 1 ∼ N。每家外卖店都有 一个优先级，初始时 (0 时刻) 优先级都为 0。

每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减 到 0；而如果外卖店有订单，则优先级不减反加，每有一单优先级加2。

如果某家外卖店某时刻优先级大于5，则会被系统加入优先缓存中；如果 优先级小于等于3，则会被清除出优先缓存。

给定 T 时刻以内的 M 条订单信息，请你计算 T 时刻时有多少外卖店在优先缓存中。

【输入格式】

第一行包含 3 个整数 N、M 和 T。

以下 M 行每行包含两个整数 ts 和 id，表示 ts 时刻编号 id 的外卖店收到 一个订单。

【输出格式】

输出一个整数代表答案。

【样例输入】

2 6 6
1 1
5 2
3 1
6 2
2 1
6 2

【样例输出】

1

【样例解释】

6 时刻时，1 号店优先级降到 3，被移除出优先缓存；2 号店优先级升到 6， 加入优先缓存。所以是有 1 家店 (2 号) 在优先缓存中。

【评测用例规模与约定】

对于 80% 的评测用例，1≤ N,M,T ≤10000。
对于所有评测用例，1≤ N,M,T ≤100000，1≤ts≤T，1≤id ≤ N。

时间限制：1.0s

内存限制：512.0MB
 

import java.util.ArrayList;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int N, M, T;N = in.nextInt(); //外卖店数M = in.nextInt();//订单数T = in.nextInt();//时刻Boolean[] level = new Boolean[N]; //判断外卖店是否处于优先队列,level[0]标志id=1的外卖店...ArrayList[] arr = new ArrayList[T]; //存放每个时刻有订单的外卖店id，如arr[0]存放ts=1时刻的订单信息...for(int i = 0; i < T; i++) {arr[i] = new ArrayList();//}for(int i = 0; i < M; i++) {int ts = in.nextInt(); int id = in.nextInt();arr[ts - 1].add(id); //ts-1为ts时刻对应的数组下标，如arr[0]保存ts=1时刻订单信息,arr[1]保存ts=2...}int[][] hunger = new int[N][2]; //hunger[i]保存id = i+1的外卖店的信息(i>=0), //hunger[i][0]保存id = i的外卖店的优先级,hunger[i][1]保存最近一次订单的时间for(int i = 0; i < T; i++) {//遍历每个时刻for(int id : arr[i]) { //遍历当前时刻所有订单hunger[id - 1][0] += 2; //有订单+2hunger[id - 1][1] = i; //保存订单时间}for(int j = 0; j < N; j++) { //检查每个外卖店的优先级是否要-1,hunger[j][1] //若最近一次订单时间与i不相等，说明该外卖店在当前时刻无订单if(hunger[j][1] != i && hunger[j][0] != 0) {hunger[j][0] -= 1;} //检查每个外卖店是否处于优先队列if(hunger[j][0] > 5) {level[j] = true;}else if(hunger[j][0] <= 3) {level[j] = false;}}}int res = 0;for(int i = 0; i < N; i++) {if(level[i] == true) {res++;}}System.out.println(res);in.close();}}