日志统计 | CYY's Blog

题目来源

www.acwing.com/problem/content/1240/

题目

小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 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$

输入样例

输出样例

1
2

1
3

AC代码

算法思路：

对于同一个帖子，我们可以按时刻进行排序，然后维护一个队列，每要入队一个元素时就判断，以队首为起始时刻以待加入队列元素为截止时刻的时间段是否满足题目要求的[T,T+D)时间段。如果不满足就将该队首元素出队，以队列中下一元素为起始时刻，以待加入队列元素为截止时刻，继续判断，如此循环，直到队为空或者在队中找到一个元素以其作为起始时刻以待加入元素为结束时刻的时间段满足题目要求的[T,T+D)，那么就将待加入元素加入队列，加入后再进行判断，如果队列中元素已经存在K个元素，则该帖子满足条件。

样例模拟：

1号帖子：1号帖子在0，9，10三个时刻获得点赞，首先将0时刻加入队列，当9时刻想加入队列时，进行判断0-9这个时间段是否满足要求[0-10)，通过判断可以知道是满足的所以将9时刻加入队中，然后进行判断队中元素是否满足点赞数k=2，也是满足的，所以帖子1是热帖

10号帖子：10号帖子在0，10两个时刻获得点赞，首先将0时刻加入队列，当10时刻想加入队列时，进行判断0-10这个时间段是否满足要求[0-10)，通过判断可以知道是不满足，所以将队首0时刻出队。出队后队为空，将待加入元素10时刻加入队列，随后再进行判断，队列中元素只有1个，不满足条件，进入下一次循环，但是已经没有新的元素加入了所以10号帖子不满足。

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX = 100005;

typedef pair<int,int> PII;  //(帖子id,点赞时刻ts)
queue<PII> p;               //维护一个队列
PII piis[MAX];              //储存日志
int ans[MAX];               //存储结果的数组
int main(){
    int n,d,k;
    cin>>n>>d>>k;
    for(int i = 0; i < n; i++)
        cin>>piis[i].second>>piis[i].first;

    sort(piis,piis+n);  //sort默认对x升序排序x相同对y升序排序，我这里x存的是帖子id所以是先按照帖子id进行排序，同一帖子按照时刻排序
    p.push(piis[0]);    //先将第一个元素入队
    for(int i = 1;i<n;i++){ //遍历每一个帖子的每一时刻，其实对于一个帖子已经判断满足了条件那么其他时刻的点赞就不用在判断了，我这里没写这个逻辑
        if(piis[i].first != piis[i-1].first ){  //这里是分辨不同帖子
            //如果上一帖子id与当前枚举到的帖子id相同，则将队列清空
            while(!p.empty()) p.pop();
            p.push(piis[i]);
        }else{
            //如果是同一帖子：
            if(piis[i].second-p.front().second<d){//判断以队首元素为开始时刻，以待加入元素为结束时刻的时间段是否满足条件
                p.push(piis[i]);        //满足则入队

            }else{                      //不满足循环出队，直到队空或找到满足条件的元素
                while(!p.empty()&&piis[i].second-p.front().second>=d){
                    p.pop();
                }
                p.push(piis[i]);        //循环出队后将待加入元素入队
            }

            if(p.size() >= k) ans[piis[i].first]++; //判断队中元素是否满足条件，满足则在结果数组中进行记录
        }

    }
    for(int i = 0;i<MAX;i++){
        //对结果数组进行遍历，下标表示帖子id
        if(ans[i] != 0) cout<<i<<endl;
    }
    return 0;
}