AcWing 1238. 日志统计
原题链接
中等
作者:
无双飞怪
,
2024-04-18 15:46:33
,
所有人可见
,
阅读 1
首先就是按照时间顺序排序 两个指针为时间 本质上就是799: 连续不重复的子序列
两个指针需要存both时间和编号 =>想到了用pair来存
为了去重 需要用一个bool数组
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define x first
#define y second
using namespace std;
const int N=1e5+10;
typedef pair<int,int> PII;
int sum[N];
PII q[N];
bool res[N];
int main()
{
int n,d,k;
cin>>n>>d>>k;
for(int i=0;i<n;i++)
{
cin>>q[i].x>>q[i].y;
}
sort(q,q+n);
int j=0;
for(int i=0;i<n;i++)
{
sum[q[i].y]++;
while(q[i].x-q[j].x>=d) sum[q[j++].y]--;//这里特别注意 是大于等于而不是大于 因为(过了多长时间)项数是末减初+1 而不是真正意义上的时间间隔
if(sum[q[i].y]>=k) res[q[i].y]=true;
}
for(int i=0;i<=N;i++) if(res[i]) cout<<i<<endl;
return 0;
}