[蓝桥杯]外卖店优先级

外卖店优先级
题目形貌

"饱了么"外卖系统中维护着 NN 家外卖店，编号 1
∼ NN。每家外卖店都有 一个优先级，初始时 (0 时刻) 优先级都为 0。
每颠末 1
个时间单元，如果外卖店没有订单，则优先级会减少 1
，最低减 到 0&#xff1
b;而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。
如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中&#xff1
b;如果 优先级小于即是 3，则会被清除出优先缓存。
给定 TT 时刻以内的 MM 条订单信息，请你计算 TT 时刻时有多少外卖店在优 先缓存中?
输入形貌

第一行包含 3 个整数 N,M,TN,M,T。
以下 MM 行每行包含两个整数 ts,idts,id，表示 tsts 时刻编号 idid 的外卖店收到一个订单。
其中，1
≤N,M,T≤1
05，1
≤ts≤T，1
≤id≤N1
≤N,M,T≤1
05，1
≤ts≤T，1
≤id≤N。
输出形貌

输出一个整数代表答案。
输入输出样例

示例

   输入

1. 2 6 6
2. 1
3. 1
5. 5 2
6. 3 1
8. 6 2
9. 2 1
11. 6 2

复制代码

   输出

1. 1

复制代码

   样例表明&#xff1
a;
  6 时刻时，1
号店优先级降到 3，被移除出优先缓存&#xff1
b;2 号店优先级升到 6， 加入优先缓存。所以是有 1
家店 (2 号) 在优先缓存中。
运行限制

• 最大运行时间&#xff1
  a;2s
  
• 最大运行内存: 256M
  

总通过次数: 4046  |  总提交次数: 6740  |  通过率: 60%
难度: 中等   标签: 201
9, 模拟, 省赛

方法思路

题目要求计算在T时刻处于优先缓存中的外卖店数量。外卖店的优先级随时间变革&#xff1
a;每过1
个时间单元无订单则优先级减1
（最低到0），有订单则每单优先级加2。当优先级>5时加入缓存，优先级≤3时移出缓存。解决思路如下&#xff1
a;
[list=1
]

分组处置惩罚订单&#xff1
a;将订单按店铺ID分组，每个店铺的订单按时间排序。

按时间处置惩罚订单&#xff1
a;对于每个店铺&#xff1
a;

• 处置惩罚无订单时间段&#xff1
  a;计算从上一次订单到当前订单之间的时间差，更新优先级（减少）。
  
• 检查缓存状态&#xff1
  a;若优先级≤3且之前在缓存中，则移出缓存。
  
• 处置惩罚当前订单&#xff1
  a;增长优先级（每单+2），若优先级>5则加入缓存。
  

处置惩罚末了时间段&#xff1
a;从末了一个订单到T时刻，更新优先级并检查缓存状态。

统计效果&#xff1
a;遍历所有店铺，统计T时刻在缓存中的店铺数量。

1. #include <iostream>#include <vector>#include <algorithm>using namespace std;int main() {    ios::sync_with_stdio(false);    cin.tie(nullptr);    int N, M, T;    cin >> N >> M >> T;    vector<vector<int>> orders(N + 1
2. );    for (int i &#61
3. ; 0; i < M; i++) {        int ts, id;        cin >> ts >> id;        orders[id].push_back(ts);    }    vector<bool> in_cache(N + 1
4. , false);    for (int id &#61
5. ; 1
6. ; id <&#61
7. ; N; id++) {        if (orders[id].empty()) continue;        sort(orders[id].begin(), orders[id].end());        int last &#61
8. ; 0;        int pri &#61
9. ; 0;        bool cache &#61
10. ; false;        int i &#61
11. ; 0;        while (i < orders[id].size()) {            int t &#61
12. ; orders[id][i];            int cnt &#61
13. ; 0;            while (i < orders[id].size() && orders[id][i] &#61
14. ;&#61
15. ; t) {                cnt++;                i++;            }            int gap &#61
16. ; t - last - 1
17. ;            pri &#61
18. ; max(0, pri - gap);            if (cache && pri <&#61
19. ; 3) cache &#61
20. ; false;            pri +&#61
21. ; 2 * cnt;            if (pri > 5) cache &#61
22. ; true;            last &#61
23. ; t;        }        int gap &#61
24. ; T - last;        pri &#61
25. ; max(0, pri - gap);        if (cache && pri <&#61
26. ; 3) cache &#61
27. ; false;        in_cache[id] &#61
28. ; cache;    }    int ans &#61
29. ; 0;    for (int id &#61
30. ; 1
31. ; id <&#61
32. ; N; id++) {        if (in_cache[id]) ans++;    }    cout << ans << endl;    return 0;}

复制代码

代码表明

输入处置惩罚&#xff1
a;

• 读取店铺数N、订单数M和时间T。
  
• 使用vector<vector<int>> orders存储每个店铺的订单时间。
  

订单分组与排序&#xff1
a;

• 对每个店铺的订单时间进行排序，便于按时间顺序处置惩罚。
  

处置惩罚每个店铺&#xff1
a;

• 初始化&#xff1
  a;last记录上次订单时间，pri记录当前优先级，cache记录缓存状态。
  
• 合并相同时间订单&#xff1
  a;统计同一时间点的订单数量。
  
• 处置惩罚无订单时段&#xff1
  a;计算时间差gap，更新优先级pri &#61
  ; max(0, pri - gap)。
  
• 检查缓存&#xff1
  a;若优先级≤3且之前在缓存中，则移出缓存。
  
• 处置惩罚订单&#xff1
  a;优先级增长2 * cnt，若优先级>5则加入缓存。
  
• 末了时段处置惩罚&#xff1
  a;从末了一个订单到T时刻，更新优先级并检查缓存状态。
  

统计效果&#xff1
a;

• 遍历所有店铺，统计T时刻在缓存中的店铺数量
  示例阐明
  
  输入示例&#xff1
  a;
  
  1. 2 6 6
  2. 1
  3. 1
  5. 5 2
  6. 3 1
  8. 6 2
  9. 2 1
  11. 6 2

  复制代码
• 店铺1
  &#xff1
  a;
  
  
  
  • 订单时间&#xff1
    a;[1
    , 2, 3]
    
  • 时间1
    &#xff1
    a;优先级&#61
    ;2，未加入缓存
    
  • 时间2&#xff1
    a;优先级&#61
    ;4，未加入缓存
    
  • 时间3&#xff1
    a;优先级&#61
    ;6，加入缓存
    
  • T&#61
    ;6时&#xff1
    a;优先级&#61
    ;3，移出缓存
    
  
  
• 店铺2&#xff1
  a;
  
  
  
  • 订单时间&#xff1
    a;[5, 6, 6]
    
  • 时间5&#xff1
    a;优先级&#61
    ;2，未加入缓存
    
  • 时间6&#xff1
    a;优先级&#61
    ;6，加入缓存
    
  • T&#61
    ;6时&#xff1
    a;优先级&#61
    ;6，保持在缓存
    
  
  
• 输出&#xff1
  a;1
  （店铺2在缓存中）
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao1
23.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。