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

本文主要是介绍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;
}

这篇关于AcWing 1238. 日志统计(双指针，滑动窗口)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---