蓝桥杯 16. 外卖店优先级

外卖店优先级

原题目链接

题目描述

“饱了么” 外卖系统中维护着 N 家外卖店，编号 1 ∼ N。每家外卖店都有一个优先级，初始时（0 时刻）优先级都为 0。

每经过 1 个时间单位：

• 如果外卖店没有订单，则优先级会减少 1，最低减到 0；
• 如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。

如果某家外卖店某时刻优先级 大于 5，则会被系统加入优先缓存中；
如果优先级 小于等于 3，则会被清除出优先缓存。

给定 T 时刻以内的 M 条订单信息，请你计算 T 时刻时有多少外卖店在优先缓存中？

输入描述

第一行包含 3 个整数 N M T。

接下来的 M 行，每行包含两个整数 ts id，表示 ts 时刻编号为 id 的外卖店收到一个订单。

• 1 ≤ N, M, T ≤ 10^5
• 1 ≤ ts ≤ T
• 1 ≤ id ≤ N

输出描述

输出一个整数，代表在 T 时刻优先缓存中的外卖店数量。

输入输出样例

输入

2 6 6
1 1
5 2
3 1
6 2
2 1
6 2

输出

1

样例解释

6 时刻时：

• 1 号店优先级降到 3，被移除出优先缓存；
• 2 号店优先级升到 6，加入优先缓存。

所以最终有 1 家店（2 号）在优先缓存中。

c++代码

#include<bits/stdc++.h>

using namespace std;

int main() {
    int N, M, T, ts, id, ans = 0;
    cin >> N >> M >> T;
    vector<vector<int>> time(N + 1);
    for (int i = 0; i < M; i++) {
        cin >> ts >> id;
        time[id].push_back(ts);
    }
    for (int i = 1; i <= N; i++) sort(time[i].begin(), time[i].end());
    for (int i = 1; i <= N; i++) {
        int val = 0, last = 0, key = 0;
        for (int j = 0; j < time[i].size(); j++) {
            int k = time[i][j] - last;
            if (k <= 1) {
                val += 2;
                if (val > 5) key = 1;
            }
            else {
                val = (val - (k - 1)) > 0 ? (val - (k - 1)) : 0;
                if (val <= 3) key = 0;
                val += 2;
                if (val > 5) key = 1;
            }
            last = time[i][j];
        }
        val -= (T - last);
        if (val <= 3) key = 0;
        if (key == 1) ans++;
    }
    cout << ans;
    return 0;
}//by wqs

题目解析

思路

一开始的想法是建立T个时间戳，每个时间戳都模拟一下，看看这个店在这个时间戳是否有订单，得出这个时间戳店的得分。

这个办法是O（T*N）的时间复杂度，会超时。

其实不需要建立T个时间戳，因为一个一个时间戳地判断太慢了。

例如一个店在3时刻，5时刻，9时刻有订单。

可以在5时刻直接减去(5 - 3 - 1) * 1，因为4时刻没订单，再加上2。

在9时刻直接减去(9 - 5 - 1) * 1，因为6,7,8时刻没有订单，再加上2。

这样快得多，从5-9我们一步跨越了3个时间戳，不用一个一个时间戳判断了。

具体实现

time(N + 1)， 存放每个店子的订单时间，按时间从小到大排序

for (int i = 0; i < M; i++) {
    cin >> ts >> id;
    time[id].push_back(ts);
}
for (int i = 1; i <= N; i++) sort(time[i].begin(), time[i].end());

开始模拟

for (int i = 1; i <= N; i++) {
    int val = 0, last = 0, key = 0;//val动态记录得分，last是上一个时间戳，key是判断是否在优先缓存。
    for (int j = 0; j < time[i].size(); j++) {
        int k = time[i][j] - last;//两个时间戳的距离
        if (k <= 1) {//k = 0说明，同一时间戳，有多个订单，k=1说明是连续的时间戳。
            val += 2;
            if (val > 5) key = 1;
        }
        else {//否则说明，要罚分
            val = (val - (k - 1)) > 0 ? (val - (k - 1)) : 0;//分数不低于0
            if (val <= 3) key = 0;
            val += 2;
            if (val > 5) key = 1;
        }
        last = time[i][j];
    }
    val -= (T - last);
    if (val <= 3) key = 0;
    if (key == 1) ans++;
}