AcWing 1238. 日志统计
原题链接
中等
作者:
琦...
,
2022-04-05 21:17:44
,
所有人可见
,
阅读 123
# include <bits/stdc++.h>
# define x first
# define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5+10;
PII h[N]; //.x 放时间, .y放id
int f[N], n, d, k;
bool st[N];
int main()
{
cin >> n >> d >> k;
for(int i = 0; i < n; i ++)
scanf("%d %d", &h[i].x, &h[i].y);
sort(h,h + n); //不要忘记排序
for(int i = 0, j = 0; i < n; i ++) //对于区间问题,且区间一直向前,用双指针, 且用if判断是否要移动指针,要实时跟新答案
{
int id = h[i].y;
f[id] ++;
while(h[i].x-h[j].x >= d)
{
f[h[j].y] --;
j ++;
}
if(f[id] >= k) st[id] = true;
}
for(int i = 0; i < N; i ++)
if(st[i] == true)
printf("%d\n", i);
return 0;
}