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

学校天梯赛一道好题: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;
        
    
        
        
        
    }
}


全部评论

相关推荐

2025-12-19 15:04
门头沟学院 Java
小肥罗:hr爱上你了,你负责吗哈哈
点赞 评论 收藏
分享
02-01 12:05
复旦大学 Java
腾讯的提前批大概率应该是没有笔试的,但是这个时候有相当部分的同学简历估计都没有准备好,没准备好的同学也不用急,大部分都是3月之后开,这个时候开的绝大多数都是神仙打架,问的东西也比较难,打算投递的同学也多看下计算机网络和操作系统,腾讯对这部分的知识问的比较多。另外多刷下牛客的热门题库,刷题注意刷ACM模式,和牛客的周赛题,腾讯有的部门会从这里面出原题。我是@程序员花海关注我,带你了解更多校招资讯!
程序员花海:还没有来得及准备的同学可以看下学习路线:https://www.nowcoder.com/discuss/824693499982315520?sourceSSR=users算法题:https://www.nowcoder.com/feed/main/detail/20e7a999fa04485b88340a274411ca0d?sourceSSR=users八股文:https://www.nowcoder.com/discuss/833102362771251200?sourceSSR=users简历书写方式:https://www.nowcoder.com/discuss/839907820706205696?sourceSSR=users都是以前在牛客发的文章~
软开人,秋招你打算投哪些...
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务