跳转链接
https://www.acwing.com/problem/content/1240/ 来源：第九届蓝桥杯省赛C++B组,第九届蓝桥杯省赛JAVAB组
题目描述
小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N 行。 其中每一行的格式是： ts id
表示在 ts 时刻编号 id 的帖子收到一个”赞”。 现在小明想统计有哪些帖子曾经是”热帖”。 如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞，小明就认为这个帖子曾是”热帖”。 具体来说，如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞，该帖就曾是”热帖”。 给定日志，请你帮助小明统计出所有曾是”热帖”的帖子编号。
输入格式 第一行包含三个整数 N,D,K。 以下 N 行每行一条日志，包含两个整数 ts 和 id 输出格式 按从小到大的顺序输出热帖 id。 每个 id 占一行。 数据范围 1≤K≤N≤10^5^, 0≤ts,id≤10^5^, 1≤D≤10000 输入样例 7 10 2 0 1 0 10 10 10 10 1 9 1 100 3 100 3 输出样例 1 3
题解思路
运用双指针算法 每次先将当前左指针所指的时刻被点赞的帖子id的点赞取消，然后右移左指针， 之后再右移右指针，再将当前右指针所指时刻被点赞的帖子id加上相应的点赞。
只需统计是否存在某个时间段为热帖则用开个数组记录下即可。
代码
cpp
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 100010;
typedef pair<int,int> PII;
int n, d, k, cnt[N]; //用来记录一个id号获得的赞数，表示形式为cnt[id]++;
PII p[N];
bool st[N]; //用来标记id号，因为id <= 1e5，所以可以利用遍历来输出。
int main()
{
cin >> n >> d >> k;
for(int i = 0; i < n; i++) cin >> p[i].x >> p[i].y;
sort(p, p + n); //排序时默认以first为准排序
for(int i = 0, j = 0; i <= n; i++) //双指针算法， i走在前面，j走在后面
{
int id = p[i].y;
cnt[id]++; //在i时刻,获得赞
while(p[i].x - p[j].x >= d) // 两个指针跨越的时间超过了d，早期的赞过期了
{
cnt[p[j].y]--;
j++;
}
if(cnt[id] >= k) st[id] = true;
}
for(int i = 0; i < N; i++)
if(st[i]) cout << i << endl;
return 0;
}
