【问题描述】
“饱了么”外卖系统中维护着 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。
题解:题目中规定外卖店的初始优先级为0,所以我们可以用一个数组来存储外卖店的优先级。再看样例输入,ts和id组成的数据明显为一个M行2列的二维数组,所以我们可以用一个int类型的二维数组来存储订单。外卖点优先级是根据时间顺序来加减,注意好临界值0的问题这道题还是比较简单的。
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int m,n,t;
n=sc.nextInt();
m=sc.nextInt();
t=sc.nextInt();
//level用于存放店铺优先级
int [] level=new int[n];
//nums[][0]和nums[][1]用来存放时刻和店铺编号
int[][] nums=new int[m][2];
for (int i = 0; i < m; i++) {
for (int j = 0; j < nums[0].length; j++) {
nums[i][j]= sc.nextInt();
}
}
//no为店铺编号-1
for (int no = 0; no < n; no++) {
//循环判断第i个时刻
for (int i = 1; i <= t; i++) {
//temp用来临时存储第n个店订单次数
int temp=0;
for (int j = 0; j < nums.length; j++) {
//判断是否n满足时刻i同时m-1满足店铺编号no
if (nums[j][0]==i&&nums[j][1]-1==no) {
temp++;
}
}
//对i时刻的店铺优先级进行加减
if (temp>0) {
level[no]+=(2*temp);
}
//限制最低优先级
else if(temp==0&&level[no]>1) {
level[no]--;
}
}
}
int count=0;
for (int score : level) {
if (score>=6) {
count++;
}
}
System.out.println(count);
}