题目描述

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

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

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

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

输入描述

输出描述

输出一个整数代表答案。

输入输出样例

示例

输入

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

输出

1

样例解释：

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

运行限制

• 最大运行时间：2s

• 最大运行内存: 256M

源码：

import java.util.Arrays;
import java.util.Scanner;public class 外卖店优先级 {static class message implements Comparable{int t;int id;public message(int t,int id) {super();this.t=t;this.id=id;}@Overridepublic int compareTo(message o) {if (this.id!=o.id) {return this.id-o.id;}else {return this.t-o.t;}}}public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int n=scanner.nextInt();int m=scanner.nextInt();int t=scanner.nextInt();message[] message=new message[m];for (int i = 0; i < message.length; i++) {message[i]=new message(scanner.nextInt(), scanner.nextInt());}Arrays.sort(message);int flag=0;//表示是否在优先级缓存中，在的flag=1int ans=0;//记录答案int cnt=2;//表示外卖店的优先级大小for (int i = 1; i < message.length; i++) {if (message[i].id!=message[i-1].id) {if (flag==1 && (cnt-(t-message[i-1].t))>3) {ans++;}cnt=2;flag=0;}else {int diff=message[i].t-message[i-1].t-1;//优先级降低了多少 me[i].t=1  me[i-1].t=1if(diff==-1) diff=0;cnt=Math.max(0, cnt-diff);if(cnt<=3) flag=0;cnt+=2;if(cnt>5) flag=1;}}//对最后一个订单/最后一个外卖店进行判断if (flag==1 && (cnt-(t-message[m-1].t))>3) {ans++;}System.out.println(ans);}}

先按照id和时间来排序 ，id相等的计算下优先级，不相等的初始化后再计算优先级