[蓝桥杯2018初赛]日志统计(尺取法)

描述:http://oj.ecustacm.cn/problem.php?id=1373

小明维护着一个程序员论坛。现在他收集了一份"点赞"日志，日志共有N行。
其中每一行的格式是：ts id。表示在ts时刻编号id的帖子收到一个"赞"。  
现在小明想统计有哪些帖子曾经是"热帖"。
如果一个帖子曾在任意一个长度为D的时间段内收到不少于K个赞，小明就认为这个帖子曾是"热帖"。  
具体来说，如果存在某个时刻T满足该帖在[T, T+D)这段时间内(注意是左闭右开区间)收到不少于K个赞，该帖就曾是"热帖"。  
给定日志，请你帮助小明统计出所有曾是"热帖"的帖子编号。  

---

现在再来写这道题，也很简单嘛！得意

其实我们发现只需要维护一段长度为d-1的区间就好了

那么用p1,p2两个指针

如果p2指向的那个时间减去p1指向的那个时间大于d

说明区间不满足，那么我们把p1指针右移一位，同时p1指向的帖子点赞减一

因为已经过时了

然后一旦发现哪个帖子大于k了，标记起来，最后一起输出

#include <bits/stdc++.h>
using namespace std;
struct p{
    int id,ts;
}a[100009];
bool com(p a,p b){
    return a.ts<b.ts;
}
int vis[100009],num[100009];
int n,d,k;
int main()
{
    scanf("%d%d%d",&n,&d,&k);
    for(int i=1;i<=n;i++)    scanf("%d%d",&a[i].ts,&a[i].id);
    sort(a+1,a+1+n,com);
    int p1=1,p2=1;
    for(int i=1;i<=n;i++)
    {
        num[a[i].id]++;
        if(num[a[i].id]>=k)    vis[a[i].id]=1;
        p2++;
        //区间是a[p1].ts~~a[p1].ts+d-1>=a[p2].ts 
        if(a[p2].ts-a[p1].ts>d)
        {
            num[a[p1].id]--;
            p1++;    
        }
    }
    for(int i=0;i<=100000;i++)
    {
        if(vis[i])
            cout<<i<<endl;
    }
}