日志统计(acWing,蓝桥杯)

题目：

1238. 日志统计

•    题目
•    提交记录
•    讨论
•    题解
•    视频讲解

小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 NN 行。

其中每一行的格式是：

ts id  

表示在 tsts 时刻编号 idid 的帖子收到一个”赞”。

现在小明想统计有哪些帖子曾经是”热帖”。

如果一个帖子曾在任意一个长度为 DD 的时间段内收到不少于 KK 个赞，小明就认为这个帖子曾是”热帖”。

具体来说，如果存在某个时刻 TT 满足该帖在 [T,T+D)[T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 KK 个赞，该帖就曾是”热帖”。

给定日志，请你帮助小明统计出所有曾是”热帖”的帖子编号。

输入格式

第一行包含三个整数 N,D,KN,D,K。

以下 NN 行每行一条日志，包含两个整数 tsts 和 idid。

输出格式

按从小到大的顺序输出热帖 idid。

每个 idid 占一行。

数据范围

1≤K≤N≤1051≤K≤N≤105,
0≤ts,id≤1050≤ts,id≤105,
1≤D≤100001≤D≤10000

输入样例：

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

输出样例：

1
3

难度：中等

时/空限制：1s / 64MB

总通过数：20816

总尝试数：43559

来源： 第九届蓝桥杯省赛C++ B组第九届蓝桥杯省赛Java B组

算法标签

---

挑战模式

代码：

#include <bits/stdc++.h>
using namespace std;typedef pair<int,int> PII;
const int N=1e5+10;PII logs[N];
int cnt[N];//记录每个id的点赞数
bool st[N];//用来标记id号，因为id <= 1e5，所以可以利用遍历来输出。int main(){int n,d,k;cin>>n>>d>>k;for(int i=0;i<n;i++){cin>>logs[i].first>>logs[i].second;}//对时刻进行排序sort(logs,logs+n);//i在前面,j在后面。区间[j,i]表示时间间隔为d。双指针是对应的时刻。int i,j;for(i=0,j=0;i<n;i++){int t=logs[i].second;//记录下此刻帖子的idcnt[t]++;//点赞数量++while(logs[i].first-logs[j].first>=d){//当时间间隔大于d时说明超出窗口的长度，移动j++。等于d，但是区间要求是左闭右开，i此刻取到了，但不应该取到，所以减小区间,j++cnt[logs[j].second]--;//去掉j时刻所指的id赞数j++;}if(cnt[t]>=k) st[t] = true;//为什么不直接输出，有可能会重复，在一个区间内满足了，另一个区间内该id又满足了。所以直接加st数组判断就行//也可用用set<int> result数组存储id，set集合有序唯一。。 result.insert(t);for (int t : result) 输出t}for (int i = 0; i <= 100000; i ++ ) if (st[i]) cout << i << endl;return 0;
}

思路：

该题的标签提示我是双指针和滑动窗口；

时间范围内点赞，可用考虑先排序对时间。由于ts与id是一一对应的，而且还要排序，所以可用pair来表示       pair<int,int> logs;logs[i].first,logs[i].second;

双指针：j,i左右指针指向一个时刻区间

滑动窗口：[T,T+D)时间，时间间隔小于d