菜狗的第一篇题解
(STL基础+快排+滑动窗口)
时间复杂度
$O(NlogN)$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
struct node{
int ts;//时刻
int id;//编号
bool operator <(const node &a) const{
return id<a.id||(id==a.id&&ts<a.ts);
}//重载运算符,使得先依id序号由小到大排序,在序号相同时,再按照时间从小到大排序
}tz[100050];//帖子
int n,d,k;
map<int,int> mp,ans;
//map主要作用是为了防止重复,其实变量+数组能轻松替换
queue<int> q;
//队列维护的是一个编号的对于当前所判段的时刻所满足的从小到大的时刻们
int main(){
ios;//提高运算速度
cin>>n>>d>>k;//普普通通的输入
for(int i=1;i<=n;i++) cin>>tz[i].ts>>tz[i].id;//结构体读入
sort(tz+1,tz+1+n);//结构体快排
//快排复杂度平均一般算O(NlogN)
for(int i=1;i<=n;i++){
if(!mp.count(tz[i].id)){//轮到一个新的编号了
mp.insert({tz[i].id,1});//标记该编号已经开始判断了
while(!q.empty()) q.pop();//清空队列
q.push(tz[i].ts);//队列的第一个元素
}
else{
while(!q.empty()&&q.front()+d<=tz[i].ts) q.pop();
//滑动窗口的原理,因为时刻都是单调增加的,所以将前面那些超过时刻的都出队
q.push(tz[i].ts);
}
if(!ans.count(tz[i].id)&&q.size()>=k) ans.insert({tz[i].id,1});
//用map类型来存储,可以简单地防止重复
//由于已经是排序好的状态,所以将结果存进ans时已经确保为从小到大了
//对于每个元素都是进队列一次出队列一次,所以该for循环仍为O(N)复杂度
}
for(auto &i:ans) cout<<i.first<<endl;
//用auto来输出合格的那些编号
return 0;
}