当前位置: 首页 > 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标准。该标准旨…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...