第九届蓝桥杯省赛 C++ B组 - 日志统计
✍个人博客:https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址:蓝桥杯题解集合
📝原题地址:日志统计
📣专栏定位:为想参加蓝桥杯的小伙伴整理常考算法题解,祝大家都能取得理想成绩!
❤️如果有收获的话,欢迎点赞👍收藏📁,您的支持就是我创作的最大动力💪
问题描述
小明维护着一个程序员论坛。现在他收集了一份”点赞”日志,日志共有 N 行。
其中每一行的格式是:
ts id表示在 ts 时刻编号 id 的帖子收到一个”赞”。
现在小明想统计有哪些帖子曾经是”热帖”。
如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞,小明就认为这个帖子曾是”热帖”。
具体来说,如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞,该帖就曾是”热帖”。
给定日志,请你帮助小明统计出所有曾是”热帖”的帖子编号。
输入格式
第一行包含三个整数 N,D,K。
以下 N 行每行一条日志,包含两个整数 ts 和 id。
输出格式
按从小到大的顺序输出热帖 id。
每个 id 占一行。
数据范围
1≤K≤N≤105,
0≤ts,id≤105,
1≤D≤10000输入样例:
7 10 2 0 1 0 10 10 10 10 1 9 1 100 3 100 3输出样例:
1 3
思路
具体思路如下:
- 将输入的日志按照时间从小到大进行排序。
- 枚举每一条日志,用一个数组 cnt 来记录当前时间间隔内每个 id 的点赞数。同时将已经不在热度规定时间间隔内的帖子减去相应的点赞,保证 cnt 中记录的点赞数是在时间间隔内的。如果在热度规定的时间间隔内点赞数大于等于 k,则在 st 中标记该 id 为热帖即标记为 true。
- 遍历 st 数组,如果为 true 则输出相应的 id。
我们举个例子,假设 n=7, d=5, k=3,看一看该过程的中间部分:

可以发现当时间窗口长度刚好为 5 时,id 为 1 的帖子满足了热帖的要求,所以在 st 中将其标记为热帖。然后我们继续往后操作即 i 继续增加,发现时间窗口长度超过了 5,故需要将 j 往后移动,同时修改 cnt 中对应的值。

代码
#include<bits/stdc++.h>
using namespace std;typedef pair<int, int> PII;
const int N = 100010;
int n, d, k;
PII logs[N];
int cnt[N];
bool st[N] = { 0 };int main()
{cin >> n >> d >> k;for (int i = 0; i < n; i++)scanf("%d%d", &logs[i].first, &logs[i].second);//按照时间从小到大排序sort(logs, logs + n);//按照时间从小到大枚举日志for (int i = 0, j = 0; i < n; i++){int id = logs[i].second;cnt[id]++; //当前id点赞数加一//减去已经在规定热度时间间隔之外的id点赞while (logs[i].first - logs[j].first >= d){cnt[logs[j].second]--;j++;}//如果该时间间隔内点赞数已经大于等于k,则记录该热帖if (cnt[id] >= k) st[id] = true;}//输出热帖idfor (int i = 0; i <= 100000; i++)if (st[i])printf("%d\n", i);return 0;
}
相关文章:
第九届蓝桥杯省赛 C++ B组 - 日志统计
✍个人博客:https://blog.csdn.net/Newin2020?spm1011.2415.3001.5343 📚专栏地址:蓝桥杯题解集合 📝原题地址:日志统计 📣专栏定位:为想参加蓝桥杯的小伙伴整理常考算法题解,祝大家…...
记一次服务器入侵事件的应急响应
0x01 事件背景 8月某日,客户官网被黑,需在特定时间内完成整改。为避免客户业务受到影响,实验室相关人员第一时间展开本次攻击事件的应急处理。 0x02 事件分析 网站源码被篡改,攻击者一定获取到了权限,那么接下来的思…...
作用域链查找机制(回顾)
全局 / 私有变量作用域的概念作用域链 scopeChain 的概念作用域链 scopeChain 的形成函数执行步骤作用域链查找机制 全局 / 私有变量 全局变量:在全局上下文EC(G)中的全局变量对象VO(G)中,存储的变量 私有变量:在函数执行形成的私有上下文EC(XXX)中的变…...
前端基础之HTML扫盲
文章目录一. 第一个HTML程序1. 创建一个HTML文件并运行2. HTML的基本结构二. HTML常见标签1. 注释标签2. 标题标签3. 段落标签4. 换行标签5. 格式化标签6. 图片标签7. 超链接标签8. 表格标签9. 列表标签10. 表单标签10.1 input标签10.2 select标签10.3 textarea标签11. 无语义标…...
大规模食品图像识别:T-PAMI 2023论文解读
美团基础研发平台视觉智能部与中科院计算所展开科研课题合作,共同构建大规模数据集Food2K,并提出渐进式区域增强网络用于食品图像识别,相关研究成果已发表于T-PAMI 2023。本文主要介绍了数据集特点、方法设计、性能对比,以及基于该…...
【java】Spring Cloud --Spring Cloud Alibaba RocketMq 异步通信实现
文章目录介绍RocketMQ特点Spring Cloud StreamWindow搭建部署RocketMQ下载启动NameServer服务启动Broker服务示例创建 RocketMQ 消息生产者创建 RocketMQ 消息消费者使用示例示例关联项目运行示例测试介绍 RocketMQ 是一款开源的分布式消息系统,基于高可用分布式集…...
玫瑰花变蚊子血,自动化无痕浏览器对比测试,新贵PlayWright Vs 老牌Selenium,基于Python3.10
也许每一个男子全都有过这样的两个女人,至少两个。娶了红玫瑰,久而久之,红的变了墙上的一抹蚊子血,白的还是床前明月光;娶了白玫瑰,白的便是衣服上沾的一粒饭黏子,红的却是心口上一颗朱砂痣。–…...
Spring Cloud入门篇 Hello World | Spring Cloud 1
一、专栏说明 Spring Cloud是一系列框架的有序集合。它利用Spring Boot的开发便利性巧妙地简化了分布式系统基础设施的开发,如:服务发现/注册、配置中心、消息总线、负载均衡、断路器、数据监控等,都可以用Spring Boot的开发风格做到一键启动和部署。 本文主要介绍Spring C…...
C++学习笔记-数据结构
结构 是C中另一种用户自定义的可用数据类型,允许存储不同类型的数据项。 C/C 数组允许定义可存储相同类型数据项的变量,但是结构是 C 中另一种用户自定义的可用的数据类型,它允许存储不同类型的数据项。 结构用于表示一条记录,假…...
【C++的OpenCV】第五课-OpenCV图像常用操作(二):OpenCV的基本绘图、平滑滤波(模糊)处理
让我们继续一、OpenCV基本绘图1.1 OpenCV关于绘图的操作1.1.1 cv::Point()1.1.2 cv::Scalar()1.1.3 cv::line()画线1.1.4 cv::rectangle()画矩形1.1.5 cv::circle()画圆二、图像的平滑滤波处理2.1 概念2.2 OpenCV关于图像模糊的操作2.2.1 常用滤波器的分类2.2.2 各种滤波方法具…...
[SSD固态硬盘技术 19] 谁是数据的守护神? 盘内RAID1/RAID5图文详解_盘内数据冗余保护
版权声明: 付费作品,禁止转载前言提到冗余保护,最容易想到的就是RAID(Redundant Arrays of Independent Disks) , 独立冗余磁盘阵列。它是一种把多块独立的物理硬盘按不同方式组合形成一个硬盘组,以此提供比单个硬盘更高的存储性能…...
linux相对于windows环境为啥相对来说更加具有安全性
linux相对于windows环境为啥相对来说更加具有安全性 文章目录linux相对于windows环境为啥相对来说更加具有安全性前言一、linux不需要防病毒软件1.1Linux 桌面的恶意软件很少见1.2Linux 的软件安装更安全1.3Linux 保护自己免受恶意软件的侵害1.4杀毒效果存疑1.5Linux 良好的安全…...
iOS开发笔记之九十七——关于Restful API的一些总结
*****阅读完此文,大概需要3分钟******一、什么是 Restful API?Restful(Representational State Transfer表现层状态转换)是目前最流行的接口设计规范。Restful API 是一种设计风格(是设计风格而不是标准)&a…...
Linux系统Nginx下载和安装
文章目录golang学习面试网站Linux启动nginx参考Linux启动nginx版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.csdn.net/weixin_36755535/article/details/110…...
交叉编译 acl
交叉编译 acl 概述 访问控制列表(Access Control Lists,ACL)是应用在路由器接口的指令列表。在 Linux 系统中,ACL 用于设定用户针对文件的权限,而不是在交换路由器中用来控制数据访问的功能(类似于防火墙…...
wait/notify方法 等待唤醒机制
线程正在运行,调用这个线程的wait()方法,这个线程就会进入一个集合进行等待(这个集合的线程不会争抢cpu),此时线程的状态就是waiting 当有线程调用notify()方法的时候,就会从集合中挑选一个线程进入到排队队列里面 notifyAll就是…...
c++笔记之构造函数中的default作用
一、 举例: class Student {int ID;std::string sName; };Student s1; Student s2(s1); 在不定义任何构造函数的情况下,Student对象能定义成功,因为编译器会默认为我们设置几个构造函数,多的不说了,就说最简单的两个: (1) Student s1; 这个就是会调用编译器为我们…...
【代码随想录二刷】Day24-回溯-C++
代码随想录二刷Day24 今日任务 理论基础 77.组合 语言:C 理论基础 解决的问题 ① 组合问题:不考虑顺序 ② 切割问题 ③ 子集问题 ④ 排列问题:考虑顺序 ⑤ 棋盘问题:N皇后,解数独回溯法三部曲 ① 回溯函数模板返回…...
Kubernetes中YAML 文件简介
我们在安装 kubernetes 集群的时候使用了一些 YAML 文件来创建相关的资源,但是对 YAML 文件还是非常陌生。所以我们先来简单看一看 YAML 文件是如何工作的,并使用 YAML 文件来定义一个 kubernetes pod,然后再来定义一个 kubernetes deploymen…...
骨传导耳机是怎么发声的,骨传导耳机值得入手嘛
现在市面上除了我们平时比较常见的有线耳机、头戴耳机、真无线耳机,近两年还涌现出了一种有着黑科技之称的特别耳机——骨传导耳机,并且因其在运动场景下的优势过于明显而得到了众多运动爱好者的大力追捧。那么今天我们就来聊聊这款所谓的黑科技骨传导耳…...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
深度学习习题2
1.如果增加神经网络的宽度,精确度会增加到一个特定阈值后,便开始降低。造成这一现象的可能原因是什么? A、即使增加卷积核的数量,只有少部分的核会被用作预测 B、当卷积核数量增加时,神经网络的预测能力会降低 C、当卷…...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
