当前位置：首页 > article >正文

日志统计(acWing,蓝桥杯)

article 2025/2/11 3:53:21

题目：

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

输入样例：

输出样例：

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;//记录下此刻帖子的id
        cnt[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;
}