AcWing
1241. 外卖店优先级
由于订单数量、店铺数量和时间达到$10^5$，我们不能通过时间来枚举每一份订单，这样必然会超时。对于一家店铺来说，在一条时间轴上，必然是有一些时间点有订单，有些点没有订单。那么可以枚举每一批次订单，这些订单是同一时刻同一店铺的，这样的话时间复杂度就降到$O(m)$. 在枚举每一批次的订单的时候，要先处理没有收到订单的一段时间的累计效应，判断当前状态(是否优先)，再改变收到订单之后的状态。
#include <bits/stdc++.h>
using namespace std;
int n, m, t;
const int N = 100010;
typedef pair<int, int> PII;
PII ods[N];
int p[N], last[N]; // 店铺的优先级和记录优先级的时间
bool inm[N]; // 是否在缓存中
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> t;
for(int i = 1; i <= m; i++){
int ts, id;
cin >> ts >> id;
ods[i].first = ts;
ods[i].second = id;
}
sort(ods + 1, ods + 1 + m);
for(int i = 1; i <= m; ){
int j = i;
while(j <= m && ods[i] == ods[j]) j++;
int cnt = j - i, ts = ods[i].first, id = ods[i].second;
p[id] -= (ts - last[id] - 1);
if(p[id] < 0) p[id] = 0;
if(inm[id] && p[id] <= 3) inm[id] = false; // 处理ts时刻之前
p[id] += cnt * 2;
if(!inm[id] && p[id] > 5) inm[id] = true;
last[id] = ts;
i = j;
}
// 处理最后的时刻没有订单的外卖店
for(int id = 1; id <= n; id++){
p[id] -= (t - last[id]);
if(inm[id] && p[id] <= 3) inm[id] = false;
}
int res = 0;
for(int id = 1; id <= n; id++) if(inm[id]) res ++;
cout << res;
return 0;
}