[蓝桥杯 2019 省 A] 外卖店优先级

题意

有 N 家外卖店，初始优先级都为 0。

每过一个时刻：

如果某店这一时刻没有订单，优先级减 1，最低到 0；
如果这一时刻有 k 单，优先级加 2k。

同时系统维护一个“优先缓存”：

优先级 > 5 时加入缓存；
优先级 <= 3 时移出缓存。

给出 T 时刻以内的所有订单，问 T 时刻时缓存中有多少家店。

思路

最直接的做法是按时间一秒一秒模拟，再对每一秒检查每一家店。

这个版本最好理解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51#include <bits/stdc++.h>
using namespace std;

const int MAXN = 55;
const int MAXT = 55;

int n, m, T;
int cnt[MAXT][MAXN];
int score[MAXN];
bool in_cache[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> T;
    for (int i = 1; i <= m; i++) {
        int t, id;
        cin >> t >> id;
        cnt[t][id]++;
    }

    // 朴素模拟每一个时刻、每一家店。
    for (int t = 1; t <= T; t++) {
        for (int id = 1; id <= n; id++) {
            if (cnt[t][id] == 0) {
                score[id] = max(0, score[id] - 1);
            }
            else {
                score[id] += cnt[t][id] * 2;
            }

            if (score[id] > 5) {
                in_cache[id] = true;
            }
            else if (score[id] <= 3) {
                in_cache[id] = false;
            }
        }
    }

    int ans = 0;
    for (int id = 1; id <= n; id++) {
        if (in_cache[id]) {
            ans++;
        }
    }

    cout << ans << '\n';
    return 0;
}

但 N,T 都能到 10^5，这样做是 $O(NT)$ ，肯定过不去。

关键在于：一段连续时间里如果某家店一直没有订单，那么这整段时间的作用只有一件事，就是优先级不断减 1，直到降到 0。

所以我们没必要把这段空白时间逐秒展开，可以一次性处理。

只在“有订单的时刻”更新

把所有订单按 (时间, 店铺编号) 排序。

然后维护三样东西：

score[id]：这家店当前优先级；
last_time[id]：这家店上一次被处理到的时刻；
in_cache[id]：这家店当前是否在优先缓存里。

现在处理某家店在时刻 t 的一组订单，假设这一组一共有 cnt 单。

先看它从上一次处理到现在，中间空了多久：

gap = t - last_time[id] - 1

这 gap 个时刻都没有订单，所以可以一次性扣掉：

score[id] = max(0, score[id] - gap)

如果扣完后 score[id] <= 3，说明它已经不在优先缓存里了。

然后再把这一时刻的订单一起加上：

score[id] += 2 * cnt

如果新分数 > 5，就加入缓存。

别忘了补到 T 时刻

所有订单处理完之后，每家店还要再把“最后一次出现之后到 T”这一段空白时间补扣掉。

补完之后，再根据是否 <= 3 决定它会不会被移出缓存。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 5;
const int MAXM = 100000 + 5;

struct Order {
    int t;
    int id;
};

int n, m, T;
Order ord[MAXM];
int score[MAXN];
int last_time[MAXN];
bool in_cache[MAXN];

bool cmp_order(const Order &a, const Order &b) {
    if (a.t != b.t) {
        return a.t < b.t;
    }
    return a.id < b.id;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> T;
    for (int i = 1; i <= m; i++) {
        cin >> ord[i].t >> ord[i].id;
    }

    sort(ord + 1, ord + m + 1, cmp_order);

    int i = 1;
    while (i <= m) {
        int t = ord[i].t;
        int id = ord[i].id;
        int cnt = 0;

        while (i <= m && ord[i].t == t && ord[i].id == id) {
            cnt++;
            i++;
        }

        // 中间这些时刻该店没有订单，优先级会持续下降。
        score[id] = max(0, score[id] - (t - last_time[id] - 1));
        if (score[id] <= 3) {
            in_cache[id] = false;
        }

        score[id] += cnt * 2;
        if (score[id] > 5) {
            in_cache[id] = true;
        }

        last_time[id] = t;
    }

    int ans = 0;
    for (int id = 1; id <= n; id++) {
        score[id] = max(0, score[id] - (T - last_time[id]));
        if (score[id] <= 3) {
            in_cache[id] = false;
        }
        if (in_cache[id]) {
            ans++;
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

时间复杂度： $O(M log M + N)$
空间复杂度： $O(N + M)$

总结

这题的本质是“带时间轴的模拟”，关键不是状态多难，而是要识别出：

连续很多个“没订单的时刻”可以整体压缩成一次扣分。

因此做法就是：

按时间排序订单；
只在真正有订单的时刻更新对应店铺；
最后补上每家店到 T 的尾巴。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。