题目描述
[蓝桥杯 2018 省 B] 日志统计
题目描述
小明维护着一个程序员论坛。现在他收集了一份“点赞”日志,日志共有 $N$ 行。其中每一行的格式是 ts id
,表示在 $ts$ 时刻编号 $id$ 的帖子收到一个“赞”。
现在小明想统计有哪些帖子曾经是“热帖”。如果一个帖子曾在任意一个长度为 $D$ 的时间段内收到不少于 $K$ 个赞,小明就认为这个帖子曾是“热帖”。
具体来说,如果存在某个时刻 $T$ 满足该帖在 $[T,T+D)$ 这段时间内(注意是左闭右开区间)收到不少于 $K$ 个赞,该帖就曾是“热帖”。
给定日志,请你帮助小明统计出所有曾是“热帖”的帖子编号。
输入格式
第一行包含三个整数 $N$、$D$ 和 $K$。
以下 $N$ 行每行一条日志,包含两个整数 $ts$ 和 $id$。
输出格式
按从小到大的顺序输出热帖 $id$。每个 $id$ 一行。
样例 #1
样例输入 #1
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
样例输出 #1
1
3
提示
对于 $50\%$ 的数据,$1 \le K \le N \le 1000$。
对于 $100\%$ 的数据,$1 \le K \le N \le 10^5$,$0 \le id, ts \le 10^5$。
时限 1 秒, 256M。蓝桥杯 2018 年第九届省赛
(滑动窗口求解) $O(n)$
根据题意进行模拟即可。
为了方便理解,维护两个滑动窗口deque<pair<int,int>> logs
和deque<pair<int,int>> q;
。
双端队列 $logs$ 存储所有的日志,每个日志由一个时间戳和一个 $ID$ 组成,对其进行排序,可以保证时间戳小的日志在前面,方便按照时间顺序进行模拟。
创建一个哈希表 $hot$ 来存储每个 $ID$ 的点赞数,若点赞数超过点赞阈值 $k$ 就将其加入 $res$ 数组中。
以及一个双端队列 $q$ 来存储当前时间窗口内的日志
遍历排序后的 logs,对于每个日志项 $(ts,id)$,执行以下步骤:
- 使队列q内日志的时间差不大于D,如果队列 q 不为空且当前日志的时间戳 ts 与队列前端日志的时间戳之差大于或等于 D,则从 q 中移除前端日志,并在 hot 中相应减少该帖子的点赞数。
- 在 hot 中增加当前日志帖子的点赞数
- 如果该帖子的点赞数达到 K,则将其编号 id 加入结果集 res。
- 将当前日志出队, 加入队列 q。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n,d,k;
int main()
{
cin>>n>>d>>k;
deque<pair<int,int>> logs;
deque<pair<int,int>> q;
vector<int> res;
for(int i=1;i<=n;i++)
{
int ts,id;cin>>ts>>id;
logs.push_back({ts,id});
}
sort(logs.begin(),logs.end());
unordered_map<int,int> hot; //前面为id,后面为点赞数
int t = 0;
while(logs.size()!=0)
{
while(q.size()!=0 && logs.front().first - q.front().first >= d)
{
hot[q.front().second]--;
q.pop_front();
}
hot[logs.front().second]++;
if(hot[logs.front().second] >= k)
{
res.push_back(logs.front().second);
}
q.push_back(logs.front());
logs.pop_front();
}
sort(res.begin(),res.end());
res.erase(unique(res.begin(),res.end()),res.end());
for(auto x:res)
{
cout<<x<<endl;
}
return 0;
}
谢谢宝宝的题解爱你么么么
你写这个题了嘛
没写🫰🏻
难不难这个题要不要写🫰🏻
没写你谢我干嘛下头女
去💩吧
🫰🏻
好腻害好腻害好腻害