外卖店的优先级
外卖店有一个优先队列。外卖店的优先级大于5，则会被系统加入优先队列，外卖店的优先级小于等于3，则会被清楚优先队列。给出T时刻的M条订单信息，对于1~N家外卖店，算出T时刻时优先队列有多少家外卖店。规则：每家外卖店都有一个优先级，初始时(0 时刻) 优先级都为0。每经过1 个时间单位，如果外卖店没有订单，则优先级会减少1，最低减到0；而如果外卖店有订单，则优先级不减反加，每有一单优先级加2。
注意点：
- 可能所有订单处理完毕后，仍然没有到达时间T
- 同一时刻，同一家外卖店可能会有多条订单，可能会有多家外卖店受到订单
思路：
- 首先对订单排序，按照时间顺序依次处理每单（利用结构体，对sort函数写一个comp函数）
- 对于每个时刻，处理一个或多个订单，将时刻相同的订单对应的外卖店提取出来，将优先级加2，其他家外卖店优先级减1.
- 用到set的insert()和erase()函数维护优先队列
代码：
/*
注意,订单运算完后不一定到时间T了
*/
#include<iostream>
#include<vector>
#include<algorithm>
#include<memory.h>
#include<set>
using namespace std;
struct node{
int time;
int id;
bool operator == (node a){
return this->time==a.time&&this->id==a.id;
}
};
bool comp(node a,node b){
if(a.time==b.time) return a.id<b.id;
return a.time<b.time;
}
int arry[100005];
bool vis[100005];
int main()
{
memset(arry,0,sizeof(arry));
vector<node> v;
int n,m,t;
set<int> s;
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=m;i++)
{
node a;
scanf("%d%d",&a.time,&a.id);
v.push_back(a);
}
sort(v.begin(),v.end(),comp);
//for(int i=0;i<v.size();i++) cout<<v[i].time<<" "<<v[i].id<<endl;
int p=0;
for(int i=1;i<=t;i++)
{
memset(vis,false,sizeof(vis));
if(i==v[p].time){
//node temp=v[p];
while(i==v[p].time)
{
arry[v[p].id]+=2;
vis[v[p].id]=true;
if(arry[v[p].id]>5) {
s.insert(v[p].id);
}
p++;
}
for(int j=1;j<=n;j++)
{
if(!vis[j]&&arry[j]>0) {
arry[j]--;
}
if(arry[j]==3) {
s.erase(j);
}
}
}
else{
for(int j=1;j<=n;j++)
{
if(arry[j]==4) s.erase(j);
if(arry[j]>0) arry[j]--;
}
}
}
cout<<s.size()<<endl;
return 0;
}
|