P8685 [蓝桥杯 2019 省 A] 外卖店优先级 题解
思路分析
首先，对于每一家店，我们考虑到需要从时间
-
优化1： 那么此时，由于我们把有记录和没有记录的时间点都遍历了一遍，自然浪费时间，所以，我们可以只 查找这家店有记录的时间点，没有用的点，我们用减法就能求出
-
优化2：我们需要按顺序找到每一个有记录的节点，这就需要排序，那么我们来想 一种先进先出并且排序的东西 ，所以， 优先队列 就是一个好选择，对于每一家店，我们都为其准备一个 优先队列 来存储时间点
注意一点的是： 如果在本时刻，该店的优先级
代码展示
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
priority_queue<int,vector<int>,greater<int>> h[100010]; //为每一家店创造一个优先队列（小顶对）
int n, m, t;
cin >> n >> m >> t;
for(int i = 1; i<=m; i++){
int x, y;
cin >> x >> y;
h[y].push(x);//把时间点存入这家店的队列中
}
int cnt = 0;
for(int i = 1; i<=n; i++){
int pri = 0; //“优先级”
int lastget = 0; //上一次订单的时间
bool in = false; //是否在“优先推荐”中
while(!h[i].empty()){
int x = h[i].top(); //订单时间
h[i].pop();
if(lastget!=x) pri-=(x-lastget-1);//如果不是同一个时间点多个订单的话，减去没有订单的那些时间需要减去的“优先级”
if(pri<0) pri = 0; //可能小于零，设置成零
if(in&&pri<=3) in = false; //如果在推荐里，但是此时“优先级”小于等于3，踢出推荐中
pri+=2; //拿到两点“优先级”
lastget = x; //更新上一次时间
if(pri>5) in = true; //如果此时“优先级”大于3，踢出推荐中
}
//注意的是，这里需要先判断是否被踢出推荐，然后再加上2，
//因为加入的条件是大于5，退出的条件是小于等于3，如果此时小于等于3了，但是加上2之后不小于3了，按照程序，符合“在推荐中+没有小于等于3”，不会被踢出去，
//但是由于在这些空余的时间里，已经出了推荐榜，如果再进，需要大于5，此时没有达到在加入的条件，没有在推荐榜中
//这里，由于要看的是时间T，但是T有可能不是最后一次收到订单的时间，需要额外判断，方法同上
if(lastget!=t) pri-=(t-lastget);
if(in&&pri<=3) in = false;
if(in){
cnt++;
}
}
cout << cnt;
return 0;
}