题目描述

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

算法

大概思路：

假设某店铺拿到订单的时刻分别为t1, t2, t3, t4(假设已经按照非递减序排序)，问第t4时刻店铺的优先级(根据题目t4>=t1,t2,t3)
解：

• 总共需要计算2个部分:
  • 第一部分：1 ~ t1-1， t1+1 ~ t2-1， t2+1 ~ t3-1， t3+1 ~ t4-1， t4+1 ~ T，这几个部分是没有订单的时刻,需要减去这些个时刻
  • 第二部分：t1, t2, t3,t4 这几个时刻是接到接到订单的时刻，这几个时刻分别加2
• 需要注意的是，如果同一时间有多个订单，假如上述的非递减序列中，t2 == t3，思路如下：
  • 第一部分：1 ~ t1-1， t1+1 ~ t2-1， t3+1 ~ t4-1， t4+1 ~ T，这几个部分是没有订单的时刻,需要减去这些个时刻
  • 第二部分：t1, t2, t4 这几个时刻是接到接到订单的时刻，这几个时刻分别加上该时刻订单数量cnt*2（cnt[t1] = 1, cnt[t2] = 2, cnt[t4] = 1）

具体步骤：

• 输入的$m$个订单信息，排序（时间$t$为第一优先级，订单$id$为第二优先级）
• $for$遍历订单信息（记得此时订单大体是按照时间顺序排的）。
  • 假设当前订单为第$i$个，循环判断后面有没有相同的订单(即$t$和$id$相等)。（有的话一定连续）
  • 当到第$j$个时订单不相同，此时相同订单的数量为$cnt = j - i$
  • 下一次$for$循环从$j$处开始遍历
  • 记录此时的$t$和$id$, 计算$id$的优先权，有两部分
    • 第一部分，是上一个拿到订单的时间$last[id]$和$t$之间，中间没订单所以要$-1$，没订单的数量是$t - last[i] - 1$ (比如第3和第6时刻都有订单，没有订单的时候就是4,5)
    • 计算优先权，如果为负值更新为0。如果小于等于3，更新优先缓存$st[id] = false$
    • 第二部分，是此时，$t$时刻拿到订单，并且拿到的数量为$cnt$，要加上$2*cnt$
    • 计算优先权，如果大于5，更新优先缓存$st[id] = true$
  • 解释上面那个，因为此时这几个相同的订单都计算过了不需要再计算了，所以下一次循环要从$j$开始
  • 循环最后，上一次拿到订单的时间$last[id]$更新为$t$
• 如果最后一个订单时刻为T，则没问题。如果不是T，那么最后一个拿到订单时刻到T时刻的这部分减法需要手动计算，即减去最后一个订单时刻与T的差值。换而言之，如果上一个拿到订单的时间last[id]小于$T$，则优先权 减去 $T - last[id]$。注意这里不减1，因为T时刻也没订单。如果小于等于3，更新优先缓存

Java代码：

import java.io.*;
import java.util.*;

public class Main {
    static class My implements Comparable<My> {
        int t, id;
        My(int t, int id) {
            this.t = t;
            this.id = id;
        }
        @Override
        public int compareTo(My m) {
            if (t == m.t) {
                if (id > m.id) {
                    return 1;
                } else if (id < m.id) {
                    return -1;
                }
                return 0;
            }
            return t > m.t ? 1 : -1;
        }
    }
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static final int N = 100010;
    private static int[] scores = new int[N]; //第i个店优先级
    private static int[] last = new int[N]; // 第i个店上一个有订单的时刻t = last[id]
    private static boolean[] st = new boolean[N];  //是否在优先队列
    private static My[] orders = new My[N]; //结构体数组

    public static void main(String[] args) throws IOException {
        //输入数据
        String[] ss = br.readLine().split(" ");
        int n = Integer.parseInt(ss[0]);
        int m = Integer.parseInt(ss[1]);
        int T = Integer.parseInt(ss[2]);
        for (int i = 0; i < m; i++) {
            ss = br.readLine().split(" ");
            int t = Integer.parseInt(ss[0]);
            int id = Integer.parseInt(ss[1]);
            orders[i] = new My(t, id);
        }
        // 排序
        Arrays.sort(orders, 0, m);
        //循环遍历
        for (int i = 0; i < m;) {
            int j = i;
            while (j < m && orders[i].t == orders[j].t && orders[i].id == orders[j].id) 
                j++;               
            //循环是为了找到相同的订单，cnt表示相同的数量
            int id = orders[i].id, t = orders[i].t, cnt = j - i;
            i = j;

            scores[id] -= t - last[id] - 1; //中间没有订单的数量
            if (scores[id] < 0) scores[id] = 0;
            if (scores[id] <= 3) st[id] = false;
            //上面是处理t时刻之前的减， 下面处理t时刻的加
            scores[id] += cnt*2;
            if (scores[id] > 5) st[id] = true;

            last[id] = t;

        }
        //最后一个订单t时刻到结尾T那段距离，需要手动计算
        for(int i = 1; i <= n; i++){
            if(last[i] < T){
                scores[i] -= T - last[i];
                if (scores[i] <= 3) st[i] = false;
            }
        }
        //计算最终答案
        int res = 0;
        for (int i = 1; i <= n; i++) {
            if (st[i])
                res++;
        }
        bw.write(res + "\n");
        bw.close();
        br.close();
    }
}