AcWing 1238. 日志统计(详细注释易解版)
原题链接
中等
作者:
Earloar
,
2024-04-10 00:39:41
,
所有人可见
,
阅读 5
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int cnt[N],st[N];
int main()
{
int n,d,k;
scanf("%d%d%d",&n,&d,&k);
vector<pair<int,int>> v;
for(int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
v.push_back({y,x});
}
sort(v.begin(),v.end());//注意此时对id进行排序,便于后续对时间进行处理
for(int i=0,j=0;i<=n;i++)
{
int id = v[i].first,ts = v[i].second;
if(v[j].first!=id)
j=i;//假如这个时候我们发现i和j的id不一样,说明我们上一个id已经比较完了,直接换到下一个id,也就是i现在所在的id
cnt[id]++;//点赞数加一
if(cnt[id]>=k)//假如此时他已经大于等于k了,我们就要来看看他是不是符合ts的条件
{
while(ts-v[j].second>=d)//如果此时的j是年代久远的那个,不符合ts的条件,我们就删掉他
{
j++;
cnt[id]--;
}
}
if(cnt[id]>=k)//经过这一系列操作,假如他还大于等于k,那么说明他真是个热帖
st[id]=1;
}
for(int i=1;i<=N;i++)
if(st[i])
printf("%d\n",i);
return 0;
}