P8661 [蓝桥杯 2018 省 B] 日志统计【滑动窗口】

P8661 [蓝桥杯 2018 省 B] 日志统计

题目描述

小明维护着一个程序员论坛。现在他收集了一份“点赞”日志，日志共有N NN行。其中每一行的格式是ts id，表示在t s tsts时刻编号i d idid的帖子收到一个“赞”。

现在小明想统计有哪些帖子曾经是“热帖”。如果一个帖子曾在任意一个长度为D DD的时间段内收到不少于K KK个赞，小明就认为这个帖子曾是“热帖”。

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

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

输入格式

第一行包含三个整数N NN、D DD和K KK。

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

输出格式

按从小到大的顺序输出热帖i d idid。每个i d idid一行。

输入输出样例 #1

输入 #1

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

输出 #1

1 3

说明/提示

对于50 % 50\%50%的数据，1 ≤ K ≤ N ≤ 1000 1 \le K \le N \le 10001≤K≤N≤1000。

对于100 % 100\%100%的数据，1 ≤ K ≤ N ≤ 10 5 1 \le K \le N \le 10^51≤K≤N≤105，0 ≤ i d , t s ≤ 10 5 0 \le id, ts \le 10^50≤id,ts≤105。

时限 1 秒, 256M。蓝桥杯 2018 年第九届省赛

问题链接：P8661 [蓝桥杯 2018 省 B] 日志统计
问题分析：用滑动窗口（日本人称之为尺取法，意为用尺子来取其中的一段）来解决问题是一种高效率的技巧，详细的方法这里不解释。
参考链接：LQ0059 日志统计【滑动窗口】
题记：（略）

AC的C++语言程序如下：

/* LQ0059 日志统计 */#include<iostream>#include<algorithm>#include<cstring>usingnamespacestd;constintN=100000;pair<int,int>q[N];intcnt[N+1];boolst[N+1];intmain(){intn,d,k;cin>>n>>d>>k;for(inti=0;i<n;i++)cin>>q[i].first>>q[i].second;sort(q,q+n);memset(st,false,sizeofst);for(inti=0,j=0;i<n;i++){cnt[q[i].second]++;while(q[i].first-q[j].first>=d)cnt[q[j++].second]--;if(cnt[q[i].second]>=k)st[q[i].second]=true;}for(inti=0;i<=N;i++)if(st[i])cout<<i<<endl;return0;}