用队列去维护一段时间的好题(难度:***)

学校天梯赛一道好题:L2-1 陈晓剑舞(25分) - DHU-ACM

总的来说就是有一个时间区间(意思是过一天之前的数据抹除)统计有效时间段内子程序的数目
代码思路:考察STL和数据结构,每次读入一个任务包,就把其含有的所有子任务记下来,开一个mp数组,统计某个任务出现的次数,若时间过期的情况下,并且mp减小到0,说明该子任务从这段有效时间内彻底消失了,所以总的种类数ans进行减一操作,我们考虑用队列来维护一天之内的任务包,若队首元素所在的时间超过了一天则出队,并且把其所有已存入mp数组的子程序数量都减1。
#include<bits/stdc++.h>
using namespace std;
#define MAXN 300005
vector<int>vec[MAXN];
int mp[MAXN],t[MAXN];
queue<int>q;
int main(){
    int N;
    cin>>N;
    int ans=0;
    for(int i=1;i<=N;i++){
        cin>>t[i];
        while(!q.empty()&&t[q.front()]+86400<=t[i]){
            for(auto x:vec[q.front()]){
               	--mp[x];
                if(!mp[x]) --ans;
            }
            q.pop();
        }
        q.push(i);int k;cin>>k;
        while(k--){
            int x;cin>>x;++mp[x];if(mp[x]==1) ++ans;
            vec[i].push_back(x);
        }
        cout<<ans<<endl;
        
    
        
        
        
    }
}


全部评论

相关推荐

1 收藏 评论
分享
正在热议
# 牛客帮帮团来啦!有问必答 #
1151571次浏览 17149人参与
# 通信和硬件还有转码的必要吗 #
11202次浏览 101人参与
# OPPO开奖 #
19200次浏览 267人参与
# 和牛牛一起刷题打卡 #
18971次浏览 1635人参与
# 实习与准备秋招该如何平衡 #
203377次浏览 3625人参与
# 大厂无回复,继续等待还是奔赴小厂 #
4972次浏览 30人参与
# 不去互联网可以去金融科技 #
20375次浏览 255人参与
# 通信硬件薪资爆料 #
265906次浏览 2484人参与
# 国企是理工四大天坑的最好选择吗 #
2220次浏览 34人参与
# 互联网公司评价 #
97685次浏览 1280人参与
# 简历无回复,你会继续海投还是优化再投? #
25036次浏览 354人参与
# 0offer是寒冬太冷还是我太菜 #
454864次浏览 5124人参与
# 国企和大厂硬件兄弟怎么选? #
53903次浏览 1012人参与
# 参加过提前批的机械人,你们还参加秋招么 #
14644次浏览 349人参与
# 硬件人的简历怎么写 #
82286次浏览 852人参与
# 面试被问第一学历差时该怎么回答 #
19397次浏览 213人参与
# 你见过最离谱的招聘要求是什么? #
28087次浏览 248人参与
# 学历对求职的影响 #
161236次浏览 1804人参与
# 你收到了团子的OC了吗 #
538713次浏览 6386人参与
# 你已经投递多少份简历了 #
344216次浏览 4963人参与
# 实习生应该准时下班吗 #
96976次浏览 722人参与
# 听劝,我这个简历该怎么改? #
63524次浏览 622人参与
牛客网
牛客企业服务