AcWing 1241. c++ 130ms 1500kb
原题链接
简单
作者:
ycqs
,
2021-05-24 17:03:37
,
所有人可见
,
阅读 367
注意: 每个时刻都是先判断是否移出队列, 再进行优先级加减, 再判断是否移入队列
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int e[N], ne[N], h[N], idx; // 邻接表存储每家外卖店的所有订单时间
int n, m, t, ans;
int ti[N]; // 当前外卖店的所有订单时间
void add(int a, int b){
e[idx] = b; ne[idx] = h[a]; h[a] = idx ++;
}
bool is(int a){
int flag = 0, sum = 0, j = 0; // flag标记是否在优先队列
for(int i = h[a]; i != -1; i = ne[i]){
ti[j ++] = e[i];
}
sort(ti, ti + j);
for(int i = 0; i < j; i ++){
if(i == 0 || ti[i] - ti[i - 1] == 1 || ti[i] == ti[i - 1]) sum += 2; // 相邻时刻差为0或1时,优先级不会衰减
else{
sum -= ti[i] - ti[i - 1] - 1; // 计算来到此时刻时的优先级衰减
if(sum < 0) sum = 0;
if(sum <= 3) flag = 0; // 先判断是否移出
sum += 2;
}
if(sum > 5) flag = 1; // 判断是否移入
}
if(!flag) return flag; // 若最后一个时刻不在优先队列,返回0
else{
sum -= (t - ti[j - 1]); // 计算t时刻的优先级
if(sum <= 3) return false; // 判断是否移出
else return true;
}
}
int main(){
memset(h, -1, sizeof h);
scanf("%d%d%d", &n, &m, &t);
for(int i = 0; i < m; i ++){
int a, b;
scanf("%d%d", &a, &b);
add(b, a);
}
for(int i = 1; i <= n; i ++){
if(h[i] != -1 && is(i)) ans ++;
}
printf("%d", ans);
return 0;
}