题目描述
“饱了么”外卖系统中维护着 N 家外卖店，编号 1 ∼ N。每家外卖店都有 一个优先级，初始时 (0 时刻) 优先级都为 0。
每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减 到 0;而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。
如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中;如果 优先级小于等于 3，则会被清除出优先缓存。
给定 T 时刻以内的 M 条订单信息，请你计算 T 时刻时有多少外卖店在优先缓存中。
输入
第一行包含 3 个整数 N、M 和 T。
以下 M 行每行包含两个整数 ts 和 id，表示 ts 时刻编号 id 的外卖店收到一个订单。
对于 80% 的评测用例，1 ≤ N, M, T ≤ 10000。 对于所有评测用例，1 ≤ N,M,T ≤ 100000，1 ≤ ts ≤ T，1 ≤ id ≤ N。
输出
输出一个整数代表答案。
样例输入
2 6 6
1 1
5 2
3 1
6 2
2 1
6 2样例输出
1思路
1、用优先队列数组记录每一时刻的所有订单。即时刻i的所有订单存储在moment[i]队列里（由于优先队列的特性，订单种类已排好序（不能用普通队列），而且可以重复（不能用set））
2、用map记录每一时刻处在优先缓存的外卖店。
3、用store数组记录每一家外卖店的优先级。
4、比较巧妙地一点：pri变量地设立。用来实现题中（每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减 到 0;）这句话。每过一个时间点，pri++。相当于不减小1，但把0每增加1。（增加下限）
基于以上四点对题目进行模拟，即可求出答案（为map的size）。
AC代码
#include<queue>
#include<map>
#include<functional>
#include<vector>
#include<iostream>
#include<stdio.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> > moment[100001];
int store[100001]={0};
int main()
{
int n,m,t,ts,id;
cin>>n>>m>>t;
for(int i=0;i<m;i++)
{
cin>>ts>>id;
moment[ts].push(id);
}
int pri=0;
map<int,int> a;
for(int i=1;i<=t;i++)
{
pri++;
int pre,cou;
while(!moment[i].empty())
{
pre=moment[i].top();cou=0;
while(!moment[i].empty()&&pre==moment[i].top())
{
cou++;
moment[i].pop();
}
store[pre]=store[pre]<pri?pri+2*cou:store[pre]+2*cou+1;
if(store[pre]-pri>5)
{
a[pre]=store[pre];
}
}
for(map<int,int>::iterator it=a.begin();it!=a.end();)
{
if(it->second-pri<=3) a.erase(it++);
else it++;
}
}
cout<<a.size()<<endl;
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/103321.html
