表情包制作网站,广东网站建设公司哪家好,自己做的网站怎么接入微信,专门做三国战纪的网站叫什么[题目概述]
“饱了么”外卖系统中维护着 N 家外卖店#xff0c;编号 1∼N。 每家外卖店都有一个优先级#xff0c;初始时 (0 时刻) 优先级都为 0。 每经过 1 个时间单位#xff0c;如果外卖店没有订单#xff0c;则优先级会减少 1#xff0c;最低减到 0#xff1b;而如果…[题目概述]
“饱了么”外卖系统中维护着 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 ≤ 1 0 5 1 ≤ N, M, T ≤ 10^5 1≤N,M,T≤105, 1 ≤ t s ≤ T 1 ≤ ts ≤ T 1≤ts≤T, 1 ≤ i d ≤ N 1 ≤ id ≤ N 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 号) 在优先缓存中。
分析问题 本题看不出来什么算法为模拟题。 我们首先想到的就是暴力做法枚举所有时刻在每一时刻下再枚举所有店铺看次时刻是否有订单哪些点没订单有的话 店铺优先级 2 没有的话 店铺优先级 - 1如果 店铺优先级 3, 就将其状态变为否 如果 店铺优先级 5, 就将其状态变为是最后统计所有店铺中状态为是的店铺数目。这种思路比较容易想但其时间复杂度是 T * N 而数据是 1 0 5 10 ^ 5 105量级的显然会超时。优化根据店铺订单的特征来想每个店铺都是一会有单一会没单那么如果我们每次都去判断它有没有单就很浪费时间我们可以把没有订单的这些时刻放到下一次有订单是统一处理这样就会节省很多时间。那么现在的思路就是将订单读入并排序枚举订单处理同一批订单最后统计数据 部分代码解析 因为订单两个数应该是一组相互关联的数据我们可以用pair int , int来存储 #define x first // 定义一下方便后面写
#define y second
typedef pairint, 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 pairint, 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;
}本题分享就结束了此题要求对细节的把控很高要特别注意 有问题的小伙伴可以发在评论区记得点赞关注加收藏
