题目描述

“饱了么”外卖系统中维护着 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

算法1

第一步：sort排序
第二步：遍历判断n家店是否进入优先队列
最后：判断n家店在T时间点的得分情况，并重新判断有几家店进入优先队列，用st[id]布尔数组记录是否进入优先队列(true or false)
代码中有详细的注解

分析

由输入得出的中间结果：

输入 1号店得分 2号店得分

1 1     2           0
2 1     4           0
3 1     6           0
5 2     6           2
6 2                        
6 2     6           6       //同一时刻的订单，一起算的，只有一个得分结果

java 代码

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

    public static int N=100010;
    public static int last[]=new int[N];    //记录每家店当前时间点的前一个时间点,下标为店的序号
    public static int score[] = new int[N];     //记录每家店当前时间点的得分,下标为店的序号
    public static boolean st[]=new boolean[N];  //记录是否进入优先队列,下标为店的序号

    public static class Order implements Comparable<Order> {
        int time;
        int shop_id;

        public Order(int time , int shop_id) {
            // TODO Auto-generated constructor stub
            this.time=time;
            this.shop_id=shop_id;
        }

        public int compareTo(Order o1) {
            // TODO Auto-generated method stub
            return this.time-o1.time;
        }
        public int compareTo1(Order o1) {
            // TODO Auto-generated method stub
            return this.shop_id-o1.shop_id;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int T=sc.nextInt();
        Order[] orders =new Order[m];
        for(int i=0;i<m;i++) {
            orders[i]=new Order(sc.nextInt(),sc.nextInt());
        }

        Arrays.sort(orders);


        //开始遍历
        for(int i=0;i<m && orders[i].time<=T;i++) {     //如果题目所给订单的时间orders[i].time大于T，没有实际意义，反而增加时间复杂度 

            int j=i;        //经过排序后，id从小到大排序，如果在同一时刻两个订单的时间和店名id分别都相同，肯定是前后紧密连在一起的
            while(j<m && orders[j].time==orders[i].time && orders[j].shop_id==orders[i].shop_id) {
                j++;        //计算同一时刻两个订单的时间和店名id的个数
            }

            int t=orders[i].time;       //这个订单的时间
            int id=orders[i].shop_id;       //这个订单的店名

            score[id]-=t-last[id]-1;    //得出当前时刻这家店名为id的得分,last[id]为前一个时间点,
            if(score[id]<0) {       //题目要求得分>=0
                score[id]=0;
            }
            if(score[id]<=3) {
                st[id]=false;       //这家店从优先队列中出来
            }
            last[id]=t;     //更新时间

            score[id]+=(j-i)*2;     //如果一个时间点有订单，得分为2
            if(score[id]>5) {
                st[id]=true;    //得分大于5，进入优先队列
            }
            i=j-1;      //当J=m时，上面的for循环还要i++,i=m,所以当j=m时,循环结束

        }

        //得出要求的时间T内，有多少个店进入了优先队列
        for(int i=1;i<=n;i++) {     //这里遍历的是店，有n家店
            if(last[i]<T) {
                score[i]-=T-last[i];    //计算时间点last[i]到T的得分,每隔一个时间点，得分减一，就是求T和last[i]之间有多少个时间点
                //这里不用减一，T时刻没有订单
                if(score[i]<=3) {   //重新判断T时间点有多少家店在优先队列中
                    st[i]=false;
                }
            }
        }

        int res=0;
        for(int i=1;i<=n;i++) {
            if(st[i]) {
                res++;
            }
        }
        System.out.println(res);        
    }
}