用队列去维护一段时间的好题（难度：***）
学校天梯赛一道好题：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;
}
}
查看7道真题和解析
