模拟博客链接

第十届2019年蓝桥杯真题

AcWing 1241. 外卖店优先级

JavaB组第7题

分析第一个样例：

最终在6时刻时，只有外卖2在优先缓存中，答案输出1。

暴力枚举（内存超限）

时间复杂度 $O(N^2)$

枚举每一个时刻的外卖订单

AcWingMLE，10个数据过了7个，蓝桥杯满分100分拿到了90分，最后一个数据内存超限，但也是很可观的分数了。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt(), t = sc.nextInt();
        // 数组定义在全局变量 节省内存
        int[][] a = new int[t + 1][n + 1]; // 订单 i为时刻 j为外卖编号
        int[] p = new int[n + 1]; // 优先级

        for (int i = 0; i < m; i++) a[sc.nextInt()][sc.nextInt()]++;

        for (int i = 1; i < t + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (a[i][j] > 0) {
                    a[i][j] = a[i - 1][j] + a[i][j] * 2; // 加上此订单的优先级
                    if (a[i][j] > 5)
                        p[j] = 1; // 将此时刻的外卖置入优先级
                } else {
                    if (a[i - 1][j] > 0) {
                        a[i][j] = a[i - 1][j] - 1;
                        if (a[i][j] <= 3)
                            p[j] = 0;
                    }
                }
            }
        }

        int res = 0;
        for (int i = 0; i < p.length; i++) res += p[i];

        System.out.println(res);
    }
}

优化

我们每个外卖获取到订单的时刻都是离散的，中间可能过了好久才有第二个订单，其实可以把中间这一部分压缩掉，把连续的没有订单的这一段时间统一到下一次有订单的时刻来处理，或者是放在T时刻来处理：

这样做的好处是我们在去做每一个时刻的时候，只需要考虑有订单的店即可，没有订单的店就可以不用考虑了。

此时我们可以不用枚举时刻，将所有订单按时间顺序排序，每次处理一批相同的订单，只要订单的时间点和店铺id相同，我们就把它看成一个。

score[i]表示第i个店铺当前的优先级

last[i]表示第i个店铺上一次有订单的时刻

st[i]表示第i个店铺当前是否处于优先缓存中

伪代码

处理t时刻前的内容：

这样就可以把中间没有订单的时刻压缩：

score[id] -= t - last[id] - 1; // 假如第3和第6时刻都有订单 没卖东西的时间应该是4和5 所以需要减一 6-3-1=2

还要加两个判断：

if (score[id] < 0) score[id] = 0;
if (score[id] <= 3) st[id] = false; // 移出优先缓存

更新一下last：last[id] = t

处理t时刻的内容：

score[id] += cnt * 2; // 加上优先级
if (score[id] > 5) st[id] = true; // 置于优先缓存

每一个店铺最后一段时间可能都没有订单，我们还要算一下最后一段时间，last[id] ~ T之间有多长时间没有卖东西：

for (int i = 1; i <= n; i++) {
    if (last[i] < T) {
        score[i] -= T - last[i]; // 此时不用-1，因为T时刻没有订单
        if (score[i] <= 3) st[i] = false;
    }
}

求得结果：

int res = 0;
for (int i = 1; i <= n; i++) {
    if (st[i]) res++;
}
sout(res);

完整代码

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

public class Main {

    static final int N = 100010;
    static int[] score = new int[N]; // 店铺的优先级
    static int[] last = new int[N]; // 上一次有订单的时刻
    static boolean[] st = new boolean[N]; // 表示店铺是否处于优先缓存中
    static PII[] order = new PII[N]; // 订单

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

        for (int i = 0; i < m;) { // 循环为了找到相同订单
            int j = i;
            while (j < m && order[j].ts == order[i].ts && order[j].id == order[i].id) j++;
            int t = order[i].ts, id = order[i].id;
            int cnt = j - i; // 同批订单的数量
            i = j;

            // 处理t时刻之前的信息
            score[id] -= t - last[id] - 1; // 中间没有订单的数量
            if (score[id] < 0) score[id] = 0;
            if (score[id] <= 3) st[id] = false; // 移出优先缓存

            // 处理t时刻的信息
            score[id] += cnt * 2; // 加上优先级
            if (score[id] > 5) st[id] = true; // 置于优先缓存

            last[id] = t;
        }

        for (int i = 1; i <= n; i++) {
            if (last[i] < T) {
                score[i] -= T - last[i]; // 此时不用-1，因为T时刻没有订单
                if (score[i] <= 3) st[i] = false;
            }
        }

        int res = 0;
        for (int i = 1; i <= n; i++) if (st[i]) res++;

        System.out.println(res);
    }

    static class PII implements Comparable<PII> {
        int ts;
        int id;

        public PII(int ts, int id) {
            this.ts = ts;
            this.id = id;
        }

        @Override
        public int compareTo(PII o) {
            if(this.ts > o.ts)  return 1;
            if(this.ts == o.ts) {
                if (this.id > o.id) return 1;
                return -1;
            }
            return -1;
        }
    }
}