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

蓝桥杯国赛每日一题:日志统计(双指针)

题目描述:

小明维护着一个程序员论坛。现在他收集了一份”点赞”日志,日志共有 N行。

其中每一行的格式是:

ts id  

表示在 ts时刻编号 id 的帖子收到一个”赞”。

现在小明想统计有哪些帖子曾经是”热帖”。

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

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

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

输入格式

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

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

输出格式

按从小到大的顺序输出热帖 id。

每个 id占一行。

数据范围

1≤K≤N≤10^5,
0≤ts,id≤10^5,
1≤D≤10000

输入样例:
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
输出样例:
1
3

解题思路:
1.读取数据,将数据先按时间再按id从小到大进行排序;

2.遍历数据,将每次遍历到的数据++,左指针表示能达到时间限制的最低天,每次比较左右指针的时间差,如果》d则从左指针开始--,直到j<i && i.day - j.day <d;

3.判断每次右指针指向目标的赞数是否满足k要求。

4.最后遍历所有id查看是否有符合条件则输出。

参考代码:

#include <iostream>
#include <cstring>
#include <algorithm>#define x first
#define y secondusing namespace std;
typedef pair<int, int> PII;
const int N = 1e5+10;
PII logs[N];
int n,d,k;
int cnt[N];
bool st[N];int main()
{cin>>n>>d>>k;for(int i=0;i<n;i++) cin>>logs[i].x >> logs[i].y;sort(logs,logs+n);for(int i=0,j = 0;i<n;i++){int id = logs[i].y;cnt[id]++;while(j<i && logs[i].x - logs[j].x >= d){cnt[logs[j].y]--;j++;}if(cnt[id]>=k) st[id] = true;}for(int i=0;i<N;i++)if(st[i])printf("%d\n",i);return 0;    
}

 

相关文章:

蓝桥杯国赛每日一题:日志统计(双指针)

题目描述&#xff1a; 小明维护着一个程序员论坛。现在他收集了一份”点赞”日志&#xff0c;日志共有 N行。 其中每一行的格式是&#xff1a; ts id 表示在 ts时刻编号 id 的帖子收到一个”赞”。 现在小明想统计有哪些帖子曾经是”热帖”。 如果一个帖子曾在任意一个长…...

佛山MES公司(盈致mes系统服务商)助力企业实现智能制造

佛山是中国制造业著名的城市之一&#xff0c;拥有众多制造企业。随着科技的不断发展和智能制造的兴起&#xff0c;越来越多的企业开始意识到数字化生产管理的重要性&#xff0c;MES制造执行系统作为智能制造的关键技术之一&#xff0c;受到了越来越多企业的关注和应用。 在佛山…...

算法设计课第五周(贪心法实现活动选择问题)

目录 一、【实验目的】 二、【实验内容】 三、实验源代码 一、【实验目的】 &#xff08;1&#xff09;熟悉贪心法的设计思想 &#xff08;2&#xff09;理解贪心法的最优解与正确性证明之间的关系 &#xff08;3&#xff09;比较活动选择的各种“贪心”策略&#xff0c;…...

Ubuntu20.04右键打不开终端

今天用virtualbox安装了ubuntu20.04 问题&#xff1a;右键打开终端&#xff0c;怎么也打开不了&#xff01; 点了也没反应&#xff0c;或者鼠标转小圈圈&#xff0c;然后也没有反应… 解决方法&#xff1a; 1、Ctrl Alt F6 先切换到终端访问界面 mac电脑 Ctrl Alt F6 …...

XML元素

XML 元素是XML文档中的基本组成单位&#xff0c;它由开始标签、结束标签和内容组成&#xff0c;格式如下&#xff1a; <element>content</element>常见的XML元素包括&#xff1a; 根元素&#xff08;Root Element&#xff09;&#xff1a;XML文档中的最外层元素&…...

融入新科技的SLM27211系列 120V, 3A/4.5A高低边高频门极驱动器兼容UCC27284,MAX15013A

SLM27211是高低边高频门极驱动器&#xff0c;集成了120V的自举二极管&#xff0c;支持高频大电流的输出&#xff0c;可在8V~17V的宽电压范围内驱动MOSFET&#xff0c;独立的高、低边驱动以方便控制&#xff0c;可用于半桥、全桥、双管正激和有源钳位正激等拓。有极好的开通、关…...

代码随想录算法训练营Day 38| 动态规划part01 | 理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

代码随想录算法训练营Day 38| 动态规划part01 | 理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯 文章目录 代码随想录算法训练营Day 38| 动态规划part01 | 理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯理论基础一、常规题目二、解题步骤…...

CSS拟物按钮

<div class"btn">F</div>.btn {margin: 150px 0 0 150px;display: flex;justify-content: center;align-items: center;width: 100px;height: 100px;background-color: #fff;border-radius: 20px;font-size: 50px;color: #333;/* 禁止选中文本 */user-se…...

websevere服务器从零搭建到上线(三)|IO多路复用小总结和服务器的基础框架

文章目录 epollselect和poll的优缺点epoll的原理以及优势epoll 好的网络服务器设计Reactor模型图解Reactor muduo库的Multiple Reactors模型 epoll select和poll的优缺点 1、单个进程能够监视的文件描述符的数量存在最大限制&#xff0c;通常是1024&#xff0c;当然可以更改数…...

解决宝塔Nginx和phpMyAdmin配置端口冲突问题

问题描述 在对基于宝塔面板的 Nginx 配置文件进行端口修改时&#xff0c;我注意到 phpMyAdmin 的端口配置似乎也随之发生了变化&#xff01; 解决方法 官方建议在处理 Nginx 配置时&#xff0c;应避免直接修改默认的配置文件&#xff0c;以确保系统的稳定性和简化后续的维护…...

光伏EPC管理软件都有哪些功能和作用?

光伏EPC管理软件是用于光伏工程项目管理的综合性工具&#xff0c;它涵盖了从项目策划、设计、采购、施工到运维的各个环节。 1、项目总览 管理所有项目计划&#xff0c;包括项目类型、项目容量等。 调整和优化项目计划&#xff0c;以应对不可预见的情况。 2、施工管理 制定…...

BGP学习一:关于对等体建立和状态组改变

目录 一.BGP基本概念 &#xff08;1&#xff09;.BGP即是协议也是分类 1.早期EGP 2.BGP满足不同需求 3.BGP区域间传输的优势 &#xff08;1&#xff09;安全性——只传递路由信息 &#xff08;2&#xff09;跨网段建立邻居 4.BGP总结 5.BGP的应用 &#xff08;1&#…...

ETL工具kettle(PDI)入门教程,Transform,Mysql->Mysql,Csv->Excel

什么是kettle&#xff0c;kettle的下载&#xff0c;安装和配置&#xff1a;ETL免费工具kettle(PDI)&#xff0c;安装和配置-CSDN博客 mysql安装配置&#xff1a;Linux Centos8 Mysql8.3.0安装_linux安装mysql8.3-CSDN博客 1 mysql -> mysql 1.1 mysql CREATE TABLE user_…...

常见地图坐标系间的转换算法JavaScript实现

文章目录 🍉 不同的地图厂商使用不同的坐标系来表示地理位置。以下简述:🍉 前置常量和方法:🍉 BD-09转GCJ-02(百度转谷歌、高德)🍉 GCJ-02转BD-09(谷歌、高德转百度)🍉 WGS84转GCJ-02(WGS84转谷歌、高德)🍉 GCJ-02转WGS84(谷歌、高德转WGS84)🍉 BD-09转wgs84坐…...

基于python的大麦网自动抢票工具的设计与实现

基于python的大麦网自动抢票工具的设计与实现 Design and Implementation of Da Mai Net Ticket Grabbing tool based on Python 完整下载链接:基于python的大麦网自动抢票工具的设计与实现 文章目录 基于python的大麦网自动抢票工具的设计与实现摘要第一章 引言1.1 研究背景…...

2024年5月树莓集团快讯

树莓集团近期快讯 1 园区专场招聘会进校园 国际数字影像产业园联合四川城市职业学院的专场招聘会成功召开&#xff0c;共计提供400余个工作岗位。 2 园区硬件优化再升级 园区硬件优化再升级&#xff0c;智能门禁系统及人脸识别系统下周投入使用。 3 基地短剧合作交流 天府…...

网站localhost和127.0.0.1可以访问,本地ip不可访问解决方案

部署了一个网站, 使用localhost和127.0.0.1加端口号可以访问, 但是使用本机的ip地址加端口号却不行. 原因可能有多种. 可能的原因: 1 首先要确认是否localhost对应的端口是通的(直接网址访问), 以及你无法访问的那个本机ip是否正确(使用ping测试)&#xff1b; 2 检查本机的防火…...

Docker Dockerfile如何编写?

Dockerfile 是一个用来构建镜像的文本文件&#xff0c;文本内容包含了一条条构建镜像所需的指令和说明。 1.指令说明 FROM&#xff0c;构建镜像基于哪个镜像 MAINTAINER&#xff0c;镜像维护者姓名或邮箱地址 RUN&#xff0c;构建镜像时运行的指令 CMD&#xff0c;运行容器时执…...

Python数独游戏

数独&#xff08;Sudoku&#xff09;是一种逻辑性的数字填充游戏&#xff0c;玩家需要在一个分为九宫的81格网格上填入数字&#xff0c;同时满足每一行、每一列以及每个宫&#xff08;3x3的子网格&#xff09;的数字都不重复。 在Python中实现一个数独游戏可以涉及到多个方面&…...

24 | MySQL是怎么保证主备一致的?

MySQL 主备的基本原理 内部流程 备库 B 跟主库 A 之间维持了一个长连接。主库 A 内部有一个线程,专门用于服务备库 B 的这个长连接。一个事务日志同步的完整过程是这样的: 在备库 B 上通过 change master 命令,设置主库 A 的 IP、端口、用户名、密码,以及要从哪个位置开始…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...