青岛网页建站模板,seo入门教程,厦门网站建设 php,网站建设捌金手指花总二八目录 题目链接
一些话
流程
套路
ac代码 题目链接 1241. 外卖店优先级 - AcWing题库 一些话 流程
// // 每经过 1 // 个时间单位#xff0c;如果外卖店没有订单#xff0c;则优先级会减少 1 // #xff0c;最低减到 0 // #xff1b;而如果外卖店有订单#xff0c;则…目录 题目链接
一些话
流程
套路
ac代码 题目链接 1241. 外卖店优先级 - AcWing题库 一些话 流程
// // 每经过 1 // 个时间单位如果外卖店没有订单则优先级会减少 1 // 最低减到 0 // 而如果外卖店有订单则优先级不减反加每有一单优先级加 2 // 。
// 如果某家外卖店某时刻优先级大于 5 // 则会被系统加入优先缓存中如果优先级小于等于 3 // 则会被清除出优先缓存。
// 得出结果的主要流程作为题目的切入点
// // 2 6 6 // 1 1 // 5 2 // 3 1 // 6 2 // 2 1 // 6 2 // 输入无序需要读入后排序数据是绑定的二元组用数组读入排序的话会打乱数据结构这里要用pair来储存数据然后排序
// 很容易想到 排序后直接按照题目描述从1到t模拟每个时间发生的事但复杂度是t*n1e10超时了得优化下流程 // 用一个数组记录店铺优先度一个数组记录店铺接到上一个订单的时间一个bool数组记录店铺是否在优先缓存 // 直接枚举输入里的事件通过枚举到的接到订单店铺的时间和该店铺上次接到订单的时间来确定减去了多少优先度按照时间顺序 // 是先减去这个部分的优先度再加上这次订单的优先度。枚举完所有订单事件后就开始枚举店铺这是要减去到结束时间之前的时间段失去的优先度 // 用最终时间减去每个店铺最后记录到的订单时间就能得到最后的这段时间店铺失去的优先度。每次优先度变化后进行优先缓存的判断 // 最后再遍历一遍记录店铺缓存状态的bool数组cnt计数输出 套路 ac代码
// 950~10:08// 1504~15:21
#include iostream
#include cstring
#include cstdio
#include algorithm
using namespace std;
typedef pairint,int PII;const int N 1e5 10;
int last[N],v[N];
bool st[N];
PII f[N];
int main(){int n,m,t;cin n m t;for(int i 0; i m;i){int a,b;scanf(%d%d,a,b);f[i] {a,b};}sort(f,fm);for(int i 0;i m;){int j i;while(f[i] f[j] j m) j;// 必定动一次所以后面的cntj-i而不是j-i1int cnt j - i,id f[i].second,time f[i].first; i j;v[id] - (time - last[id] - 1);// cout v[id] id endl;// cout cnt endl;if(v[id] 0) v[id] 0;if(v[id] 3) st[id] false;v[id] cnt * 2;if(v[id] 5) st[id] true;last[id] time;// cout v[id] id endl;}for(int i 1;i n;i){v[i] - t - last[i];if(v[i] 3) st[i] false;}int ans 0;for(int i 1;i n;i){if(st[i]) ans;// cout i endl;}cout ans endl;return 0;
}
