用队列去维护一段时间的好题(难度:***)
学校天梯赛一道好题: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; } }