当前位置：首页 > news >正文

AcWing 1241. 外卖店优先级（复杂模拟思路 + 代码详解）

news 2025/7/9 20:25:01

[题目概述]

“饱了么”外卖系统中维护着 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 \leq t s \leq T$ ,
$1 \leq i d \leq N$

输入样例：

输出样例：

样例解释

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

分析问题
本题看不出来什么算法，为模拟题。
1. 我们首先想到的就是暴力做法，枚举所有时刻，在每一时刻下再枚举所有店铺，看次时刻是否有订单，哪些点没订单，有的话 店铺优先级 + 2 ，没有的话 店铺优先级 - 1，如果 店铺优先级 <= 3, 就将其状态变为否，如果 店铺优先级 > 5, 就将其状态变为是，最后统计所有店铺中状态为是的店铺数目。
2. 这种思路比较容易想，但其时间复杂度是 T * N ，而数据是 $10 ^ 5$ 量级的，显然会超时。
3. 优化：根据店铺订单的特征来想，每个店铺都是一会有单，一会没单，那么如果我们每次都去判断它有没有单就很浪费时间，我们可以把没有订单的这些时刻放到下一次有订单是统一处理，这样就会节省很多时间。
4. 那么现在的思路就是，将订单读入并排序，枚举订单，处理同一批订单，最后统计数据

部分代码解析

因为订单两个数应该是一组相互关联的数据，我们可以用pair <int , int>来存储

#define x first // 定义一下方便后面写
#define y second
typedef pair<int, int> PII;
PII order[N];

处理一批订单（时刻相同且店铺号相同）
最后一定要更新 last[i]

// 枚举所有订单
for (int i = 0; i < m;) {// 处理一批订单（按顺序处理一批同一时刻，同一商家的订单）int j = i;while (j < m && order[j] == order[i])j ++;int id = order[i].y; // 店铺号int t = order[i].x; // 时刻int cnt = j - i; // 同一批的订单数量i = j;score[id] -= t - last[id] - 1;if (score[id] < 0)score[id] = 0;if (score[id] <= 3)st[id] = false;// ------------------------------以上都是处理的没有订单的时候		score[id] += cnt * 2;if (score[id] > 5)st[id] = true;last[id] = t;
}

完整代码（注释版）


#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define x first
#define y second
using namespace std;const int N = 100005;
typedef pair<int, int> PII;
int score[N], last[N]; // 分别表示每个店铺的优先级和上一次订单出现的时间
bool st[N]; // 表示店铺是否在优先缓存中
PII order[N];
int n, m, T;
int main () {scanf("%d %d %d", &n, &m, &T);// 把每个订单读入for (int i = 0; i < m ; i ++)scanf("%d %d", &order[i].x, &order[i].y);// pair对的排序方式是先按第一个元素升序排列，相同的话就比较第二个元素sort(order, order + m);// 枚举所有订单for (int i = 0; i < m;) {// 处理一批订单（按顺序处理一批同一时刻，同一商家的订单）int j = i;while (j < m && order[j] == order[i])j ++;int id = order[i].y; // 店铺号int t = order[i].x; // 时刻int cnt = j - i; // 同一批的订单数量i = j;score[id] -= t - last[id] - 1;if (score[id] < 0)score[id] = 0;if (score[id] <= 3)st[id] = false;
// ------------------------------以上都是处理的没有订单的时候		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];if (score[i] < 0)score[i] = 0;if (score[i] <= 3)st[i] = false;}}int res = 0;for (int i = 1; i <= n; i ++) {if (st[i])res ++;}cout << res << endl;return 0;
}