AcWing 1238. 日志统计(双指针，滑动窗口)

题目：

1238. 日志统计 - AcWing题库

?

数据范围

输入样例：

7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3

输出样例：

1
3

思路：双指针?

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef pair<int, int>PII;
#define x first
#define y second
const int N = 1e5 + 10;
int n, d, k;
PII logs[N];//储存数据信息
int cnt[N];//记录每个贴在单位时间内点赞数
bool st[N];//是否为热帖
int main()
{
	cin >> n >> d >> k;
	for (int i = 0; i < n; i++)scanf("%d%d", &logs[i].x, &logs[i].y);
	sort(logs, logs + n);//按照时间和编号排序
	
	//双指针i，j控制滑动窗口
	for (int i = 0,j=0;j<n;j++) //并非无脑遍历，而是根据输入遍历
	{
		while (logs[j].x-logs[i].x>=d) { cnt[logs[i].y]--;i++;}//破窗了，把最前面的踢出（类似于队列的操作）
		cnt[logs[j].y]++;
		if (cnt[logs[j].y] >= k)st[logs[j].y] = true;
	}
	
	//输出
	for (int i = 0; i < N; i++) if (st[i])printf("%d\n", i);
	return 0;
}