[蓝桥杯]外卖店优先级

外卖店优先级

题目描述

"饱了么"外卖系统中维护着 NN 家外卖店，编号 1 ∼ NN。每家外卖店都有 一个优先级，初始时 (0 时刻) 优先级都为 0。

每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减 到 0；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。

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

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

输入描述

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

以下 MM 行每行包含两个整数 ts,idts,id，表示 tsts 时刻编号 idid 的外卖店收到一个订单。

其中，1≤N,M,T≤105，1≤ts≤T，1≤id≤N1≤N,M,T≤105，1≤ts≤T，1≤id≤N。

输出描述

输出一个整数代表答案。

输入输出样例

示例

输入

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

输出

1

样例解释：

6 时刻时，1 号店优先级降到 3，被移除出优先缓存；2 号店优先级升到 6， 加入优先缓存。所以是有 1 家店 (2 号) 在优先缓存中。

运行限制

• 最大运行时间：2s
• 最大运行内存: 256M

总通过次数: 4046  |  总提交次数: 6740  |  通过率: 60%

难度: 中等   标签: 2019, 模拟, 省赛

方法思路

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

1. 分组处理订单：将订单按店铺ID分组，每个店铺的订单按时间排序。

2. 按时间处理订单：对于每个店铺：

   • 处理无订单时间段：计算从上一次订单到当前订单之间的时间差，更新优先级（减少）。

   • 检查缓存状态：若优先级≤3且之前在缓存中，则移出缓存。

   • 处理当前订单：增加优先级（每单+2），若优先级>5则加入缓存。

3. 处理最后时间段：从最后一个订单到T时刻，更新优先级并检查缓存状态。

4. 统计结果：遍历所有店铺，统计T时刻在缓存中的店铺数量。

   #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);
       for (int i = 0; i < M; i++) {
           int ts, id;
           cin >> ts >> id;
           orders[id].push_back(ts);
       }
   
       vector<bool> in_cache(N + 1, false);
       for (int id = 1; id <= N; id++) {
           if (orders[id].empty()) continue;
   
           sort(orders[id].begin(), orders[id].end());
           int last = 0;
           int pri = 0;
           bool cache = false;
   
           int i = 0;
           while (i < orders[id].size()) {
               int t = orders[id][i];
               int cnt = 0;
               while (i < orders[id].size() && orders[id][i] == t) {
                   cnt++;
                   i++;
               }
   
               int gap = t - last - 1;
               pri = max(0, pri - gap);
               if (cache && pri <= 3) cache = false;
   
               pri += 2 * cnt;
               if (pri > 5) cache = true;
   
               last = t;
           }
   
           int gap = T - last;
           pri = max(0, pri - gap);
           if (cache && pri <= 3) cache = false;
   
           in_cache[id] = cache;
       }
   
       int ans = 0;
       for (int id = 1; id <= N; id++) {
           if (in_cache[id]) ans++;
       }
       cout << ans << endl;
   
       return 0;
   }

   代码解释

5. 输入处理：

   • 读取店铺数N、订单数M和时间T。

   • 使用vector<vector<int>> orders存储每个店铺的订单时间。

6. 订单分组与排序：

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

7. 处理每个店铺：

   • 初始化：last记录上次订单时间，pri记录当前优先级，cache记录缓存状态。

   • 合并相同时间订单：统计同一时间点的订单数量。

   • 处理无订单时段：计算时间差gap，更新优先级pri = max(0, pri - gap)。

   • 检查缓存：若优先级≤3且之前在缓存中，则移出缓存。

   • 处理订单：优先级增加2 * cnt，若优先级>5则加入缓存。

   • 最后时段处理：从最后一个订单到T时刻，更新优先级并检查缓存状态。

8. 统计结果：

   • 遍历所有店铺，统计T时刻在缓存中的店铺数量

     示例说明

     输入示例：

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

   • 店铺1：

     • 订单时间：[1, 2, 3]

     • 时间1：优先级=2，未加入缓存

     • 时间2：优先级=4，未加入缓存

     • 时间3：优先级=6，加入缓存

     • T=6时：优先级=3，移出缓存

   • 店铺2：

     • 订单时间：[5, 6, 6]

     • 时间5：优先级=2，未加入缓存

     • 时间6：优先级=6，加入缓存

     • T=6时：优先级=6，保持在缓存

   • 输出：1（店铺2在缓存中）