当前位置: 首页 > news >正文

【蓝桥杯】日志统计

日志统计(编程题)https://dashoj.com/d/lqbproblem/p/53https://dashoj.com/d/lqbproblem/p/53https://dashoj.com/d/lqbproblem/p/53

题目

日志统计(编程题)

讲解

这个讲解感觉比较通俗易懂。

蓝桥杯2018年省赛B组08(c/c++)日志统计_哔哩哔哩_bilibili努力学习, 视频播放量 1641、弹幕量 0、点赞数 24、投硬币枚数 8、收藏人数 15、转发人数 3, 视频作者 昨晚梦到有鸽子落在你肩上, 作者简介 考研小朋友,相关视频:乘积最大 --蓝桥杯2018年c/c++B组10,分数 蓝桥杯2018年省赛c/c++A01,蓝桥杯2018 星期一,红客联盟真有那么神?83小时深搜保卫战揭秘,【蓝桥杯】学会暴力拿下省一!,2024.1.19第十四届蓝桥杯EDA省赛真题(作业评讲3),蓝桥杯基础算法:一维差分,蓝桥杯~三升序列,美国要把TP-LINK禁了,这事实在不知该从哪里吐槽,2025年了,我们应该如何看待C++语言?https://www.bilibili.com/video/BV19i4y1377m?vd_source=f93e63f88343133e9467ba52a1737210https://www.bilibili.com/video/BV19i4y1377m?vd_source=f93e63f88343133e9467ba52a1737210https://www.bilibili.com/video/BV19i4y1377m?vd_source=f93e63f88343133e9467ba52a1737210

题目描述

小明维护着一个程序员论坛。现在他收集了一份“点赞”日志,日志共有 N行。其中每一行的格式是 ts id,表示在 ts时刻编号 id 的帖子收到一个“赞”。

现在小明想统计有哪些帖子曾经是“热帖”。如果一个帖子曾在任意一个长度为 D的时间段内收到不少于 K 个赞,小明就认为这个帖子曾是“热帖”。

具体来说,如果存在某个时刻 T满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K个赞,该帖就曾是“热帖”。

给定日志,请你帮助小明统计出所有曾是“热帖”的帖子编号。

输入格式

第一行包含三个整数 N、D 和 K。

以下 N 行每行一条日志,包含两个整数 ts 和 id。

输出格式

按从小到大的顺序输出热帖 id。每个 id 一行。

样例
输入数据 1
7 10 2  
0 1  
0 10    
10 10  
10 1  
9 1
100 3  
100 3
输出数据 1
1  
3
提示
  • 对于 50% 的数据,1≤K≤N≤1000。
  • 对于 100% 的数据,1≤K≤N≤10^5,0≤id,ts≤10^5

思路

双指针,滑动窗口,给id分组(按照时间从小到大的顺序)

使用pair数组分组,id虽然后输入,但要放在first,这样以id为优先排序

比如样例的

0 1  
0 10    
10 10  
10 1  
9 1
100 3  
100 3

按照id为first进行排序后

id  ts
1   0
1   9
1   10
3   100
3   100
10  0
10  10

通过循环得到每个id的begin和end,然后用自定义的judge函数进行判断这个id是否是热帖。

judge函数:核心是双指针

  • 双指针窗口初始化

    • 快指针i与慢指针j初始指向当前id的起始位置begin

    • sum记录窗口内有效点赞数,初始为0

  • 窗口滑动逻辑

    1. 窗口扩张:快指针i右移,sum++累计点赞数

    2. 阈值检测:当sum >= k时,检查窗口时间跨度p[i].y - p[j].y

      • 若时间差< d:满足热帖条件,直接返回true

      • 否则:慢指针j右移缩小窗口,sum--保持窗口大小

    3. 终止条件:快指针i超出当前id的end位置

  • 关键性质

    • 通过单调滑动窗口确保时间复杂度为O(n)

    • 依赖时间有序性(因预处理排序保证)

代码

#include<iostream>
#include<string>
#include<algorithm>using namespace std;
const int N=1e5+5;
pair<int,int>p[N];bool judge(int begin, int end);#define x first
#define y second
int n,d,k;int main() {cin>>n>>d>>k;for(int i=0;i<n;i++){cin>>p[i].y>>p[i].x;//让后输入的id放到pair数组的first位置,这样排序时以id优先}sort(p,p+n);int i=0;while(i<n){int id=p[i].x;int begin=i,end;while(id==p[i].x&&i<n)//找到每组id的起始位置和终止位置{end=i;i++;}if(judge(begin,end))//对这个id进行判断是否为热帖{cout<<p[end].x<<endl;}}return 0;
}bool judge(int begin, int end) {int i=begin,j=begin;int sum=0;while(j<=i&&i<=end)//使用双指针{sum++;if(sum>=k){if(p[i].y-p[j].y<d)return true;else{sum--;j++;}}i++;}return false;
}

相关文章:

【蓝桥杯】日志统计

日志统计&#xff08;编程题&#xff09;https://dashoj.com/d/lqbproblem/p/53https://dashoj.com/d/lqbproblem/p/53https://dashoj.com/d/lqbproblem/p/53 题目 日志统计(编程题) 讲解 这个讲解感觉比较通俗易懂。 蓝桥杯2018年省赛B组08&#xff08;c/c&#xff09;日…...

23.Word:小王-制作公司战略规划文档❗【5】

目录 NO1.2.3.4 NO5.6​ NO7.8.9​ NO10.11​ NO12​ NO13.14 NO1.2.3.4 布局→页面设置对话框→纸张&#xff1a;纸张大小&#xff1a;宽度/高度→页边距&#xff1a;上下左右→版式&#xff1a;页眉页脚→文档网格&#xff1a;勾选只指定行网格✔→ 每页&#xff1a;…...

基于单片机的智能安全插座(论文+源码)

1 系统整体方案设计 本课题基于单片机的智能安全插座设计&#xff0c;以STM32嵌入式单片机为主体&#xff0c;将计算机技术和检测技术有机结合&#xff0c;设计一款电量参数采集装置&#xff0c;实现电压、电流信号的数据采集任务&#xff0c;电压、电流和功率在上位机的显示任…...

2025年人工智能技术:Prompt与Agent的发展趋势与机遇

文章目录 一、Prompt与Agent的定义与区别(一)定义(二)区别二、2025年Prompt与Agent的应用场景(一)Prompt的应用场景(二)Agent的应用场景三、2025年Prompt与Agent的适合群体(一)Prompt适合的群体(二)Agent适合的群体四、2025年Prompt与Agent的发展机遇(一)Prompt的…...

vue2-v-if和v-for的优先级

vue2-v-if和v-for的优先级 1.v-if和v-for的作用 v-if是条件渲染&#xff0c;只有条件表达式true的情况下&#xff0c;才会渲染v-for是基于一个数组来渲染一个列表&#xff0c;在v-for的时候&#xff0c;保证给每个元素添加独一无二的key值&#xff0c;便于diff算法进行优化 …...

C++六大默认成员函数

C六大默认成员函数 默认构造函数默认析构函数RAII技术RAII的核心思想优点示例应用场景 默认拷贝构造深拷贝和浅拷贝 默认拷贝赋值运算符移动构造函数&#xff08;C11起&#xff09;默认移动赋值运算符&#xff08;C11起&#xff09;取地址及const取地址操作符重载取地址操作符重…...

基于springboot校园点歌系统

基于Spring Boot的校园点歌系统是一种专为校园场景设计的音乐点播平台&#xff0c;它能够丰富学生的校园生活&#xff0c;提升学生的娱乐体验。以下是对该系统的详细介绍&#xff1a; 一、系统背景与意义 在校园环境中&#xff0c;学生们对于音乐有着浓厚的兴趣&#xff0c;传…...

pycharm 中的 Mark Directory As 的作用是什么?

文章目录 Mark Directory As 的作用PYTHONPATH 是什么PYTHONPATH 作用注意事项 Mark Directory As 的作用 可以查看官网&#xff1a;https://www.jetbrains.com/help/pycharm/project-structure-dialog.html#-9p9rve_3 我们这里以 Mark Directory As Sources 为例进行介绍。 这…...

【Elasticsearch】文本分类聚合Categorize Text Aggregation

响应参数讲解: key &#xff08;字符串&#xff09;由 categorization_analyzer 提取的标记组成&#xff0c;这些标记是类别中所有输入字段值的共同部分。 doc_count &#xff08;整数&#xff09;与类别匹配的文档数量。 max_matching_length &#xff08;整数&#xff09;从…...

算法随笔_40: 爬楼梯

上一篇:算法随笔_39: 最多能完成排序的块_方法2-CSDN博客 题目描述如下: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢&#xff1f; 示例 1&#xff1a; 输入&#xff1a;n 2 输出&#xff1a;2 解释&am…...

【Linux探索学习】第二十七弹——信号(一):Linux 信号基础详解

Linux学习笔记&#xff1a; https://blog.csdn.net/2301_80220607/category_12805278.html?spm1001.2014.3001.5482 前言&#xff1a; 前面我们已经将进程通信部分讲完了&#xff0c;现在我们来讲一个进程部分也非常重要的知识点——信号&#xff0c;信号也是进程间通信的一…...

【数学】矩阵、向量(内含矩阵乘法C++)

目录 一、前置知识&#xff1a;向量&#xff08;一列或一行的矩阵&#xff09;、矩阵1. 行向量2. 列向量3. 向量其余基本概念4. 矩阵基本概念5. 关于它们的细节 二、运算1. 转置&#xff08;1&#xff09;定义&#xff08;2&#xff09;性质 2. 矩阵&#xff08;向量&#xff0…...

设置git区分大小写

设置git区分大小写 1.全局设置 (影响全部仓库): git config --global core.ignorecase false2.仓库级别设置 (影响当前仓库): git config core.ignorecase false3.已经提交了大小写不一致的文件处理: git mv -f OldName newName # 强制重命名 git commit -m "Fix cas…...

排序算法与查找算法

1.十大经典排序算法 我们希望数据以一种有序的形式组织起来&#xff0c;无序的数据我们要尽量将其变得有序 一般说来有10种比较经典的排序算法 简单记忆为Miss D----D小姐 时间复杂度 &#xff1a;红色<绿色<蓝色 空间复杂度&#xff1a;圆越大越占空间 稳定性&…...

Github 2025-01-31Java开源项目日报 Top10

根据Github Trendings的统计,今日(2025-01-31统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Java项目10C项目1Kotlin项目1Bazel:快速、可扩展的多语言构建系统 创建周期:3564 天开发语言:Java协议类型:Apache License 2.0Star数量:2…...

Java进阶笔记(中级)

-----接Java进阶笔记&#xff08;初级&#xff09;----- 目录 集合多线程 集合 ArrayList 可以通过List来接收ArrayList对象&#xff08;因为ArrayList实现了List接口&#xff09; 方法&#xff1a;接口名 柄名 new 实现了接口的类(); PS: List list new ArrayList();遍历…...

2025游戏行业的趋势预测

一、市场现状 从总产值的角度来看&#xff0c;游戏总产值的增长率已经放缓&#xff0c;由增量市场转化为存量市场&#xff0c;整体的竞争强度将会加大&#xff0c;技术水平不强&#xff08;开发技术弱、产品品质低、开发效率低&#xff09;的公司将会面临更大的生存的困难。 从…...

4-ET框架demo的运行

开始操作 开始运行报错 编译Unity项目 状态同步demo运行 1-设置构建参数 CodeMode&#xff1a;ClientServer EPlayMode:EditorSimulateMode 点击ReGeneratoePerojectFiles调整代码结构 2-编译 在Unity.sln下编译项目 3-运行 以帧同步模式运行 1-合端运行 1.1 修改帧同步标记 …...

kamailio源文件modules.lst的内容解释

在执行make cfg 后&#xff0c;在kamailio/src目录下有一个文件modules.lst&#xff0c;内容如下&#xff1a; # this file is autogenerated by make modules-cfg# the list of sub-directories with modules modules_dirs:modules# the list of module groups to compile cf…...

亚远景-从SPICE到ASPICE:汽车软件开发的标准化演进

一、SPICE标准的起源与背景 SPICE&#xff0c;全称“Software Process Improvement and Capability dEtermination”&#xff0c;即“软件流程改进和能力测定”&#xff0c;是由国际标准化组织ISO、国际电工委员会IEC、信息技术委员会JTC1联合发起制定的ISO 15504标准。该标准旨…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...