Acwing算法心得——街灯(差分)
大家好,我是晴天学长,差分广泛用于一段范围的加减运算,可以优化时间复杂度,需要的小伙伴请自取哦!如果觉得写的不错的话,可以点个关注哦,后续会继续更新的。💪💪💪
1 )街灯

2) .算法思路
街灯
1.创建1010大小的数组
2.接受数据,注意数组的重置
3.差分加数,前缀和复原
4.开始遍历数组
无照亮范围统计量c
为0时,c++
不为0时
res+=c/2k+1,向上取整
5.注意遍历到n+1,所以数组的n+1要赋值为1,这样结尾那段也就可以统计上。
3) .算法步骤
1.创建一个大小为1010的一维数组a,用于存储每个位置的状态。
2.使用Scanner类从标准输入读取数据,进入一个while循环,直到没有更多的输入。
在循环内部,首先通过Arrays.fill方法将数组a的所有元素重置为0。
3.读取三个整数N、M和k,分别表示矩阵的行数、列数和现代艺术作品的数量。
使用一个循环读取M个现代艺术作品的位置,对应的数组元素进行更新。对于每个位置x,计算左边界l和右边界r,然后将a[l]加1,a[r+1]减1。
4.进行前缀和复原的操作,通过一个循环遍历数组a,每个位置的值加上前一个位置的值,即得到前缀和。
5.统计满足条件的现代艺术作品数量。遍历数组a,如果当前位置的值大于0,则将累计值c除以len(2k+1)并向上取整,加到结果res中,并将c重置为0;否则,将c加1。
输出结果res。
3).代码示例
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;public class Main {static int[] a = new int[1010];public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (scanner.hasNext()) {//数组重置操作Arrays.fill(a, 0);int res = 0;int N = scanner.nextInt();int M = scanner.nextInt();int k = scanner.nextInt();//避免越界操作,跟着大佬操作,从1开始.while (M-- > 0) {int x = scanner.nextInt();int l = Math.max(1, x - k);int r = Math.min(N, x + k);a[l]++;a[r + 1]--;}//前缀和复原for (int i = 1; i <= N; i++) {a[i] += (a[i - 1]);}//统计操作double c = 0;double len = 2 * k + 1;a[N + 1] = 1;for (int i = 1; i <= N + 1; i++) {if (a[i] > 0) {res += Math.ceil(c / len);c = 0;} else {c++;}}System.out.println(res);}}
}
4).总结
- 差分的应用。
- 数组的越界问题。
试题链接:
相关文章:
Acwing算法心得——街灯(差分)
大家好,我是晴天学长,差分广泛用于一段范围的加减运算,可以优化时间复杂度,需要的小伙伴请自取哦!如果觉得写的不错的话,可以点个关注哦,后续会继续更新的。💪💪…...
streamlit执行报错WARNING,重新安装碰到问题如何解决
streamlit执行报错WARNING,重新安装碰到问题如何解决 如何解决1、卸载已经安装的程序2、再次安装程序3、出现如下yinstaller 警告问题:4、又出现“which is not on PATH”警告。5、解决方案 发现在安装的时候有很多WARNING出现,但是没有但回事…...
《C++设计模式》——行为型
前言 行为型模式是对在不同的对象之间划分责任和算法的抽象化。行为型模式不仅仅关注类和对象的结构,而且重点关注它们之间的相互作用。 Interpreter(解释器) Template Method(模板方法) GOOD:把不变的代码部分都转移到父类中,将可变的代…...
什么是原生IP?原生IP与住宅IP有何区别?
相信许多做跨境的都会接触到IP代理,比如电商平台、社媒平台、收款平台等等,都会检测IP。那也会经常听到一些词汇:原生IP、住宅IP,这两者之间有什么区别呢?什么业务需要用到呢?接下来带大家具体了解一下。 什…...
element-plus 表格-自定义样式实现
效果如下 代码如下 <template><h2>表格自定义样式</h2><div style"background-color: cadetblue; height: 600px;"><div class"regulaContainer"><el-table ref"tableRef" :data"tableData" border …...
MVCC
MVCC(Multi-Version Concurrency Control)是数据库管理系统(DBMS)中的一种技术,用于管理并发访问数据,允许多个事务同时进行而不互相干扰,同时保持数据的一致性。 MVCC 的工作原理如下…...
你不知道的JavaScript---对象
1.语法 对象可以通过两种方式定义:一种是对象字面量形式,一种是构造形式 对象字面量: var muObject {key: value }构造形式的: var myObject new Object() myObject.key value不管是使用对象字面量形式还是构造形式创建出来…...
C++项目实战——基于多设计模式下的同步异步日志系统-①-项目介绍
文章目录 专栏导读项目介绍开发环境核心技术环境搭建日志系统介绍1.为什么需要日志系统2.日志系统技术实现2.1同步写日志2.2异步写日志 专栏导读 🌸作者简介:花想云 ,在读本科生一枚,C/C领域新星创作者,新星计划导师&a…...
解决Oracle数据库中日期格式不识别的问题
在数据库开发中,我们经常需要处理日期和时间数据。当我们在Oracle数据库中执行UPDATE语句时,可能会遇到ORA-01821错误,该错误表示提供的日期格式无法被数据库识别。本文将介绍如何解决Oracle数据库中日期格式不识别的问题。 问题分析&#x…...
一生一芯13——linux设置环境变量
参考自https://baijiahao.baidu.com/s?id1753516015142083750&wfrspider&forpc 本机使用ubuntu22.04 目录 1. 读取环境变量1. 读取特定环境变量2. 读取所有环境变量 2. 设置环境变量1. 对当前用户有效2. root设置 1. 读取环境变量 1. 读取特定环境变量 在命令行中输…...
CSS笔记(黑马程序员pink老师前端)定位
定位可以让盒子自由的在某个盒子内移动位置或者固定在屏幕中某个位置,并且可以压住其他盒子。 定位 定位模式 边偏移 定位模式说明static静态定位,按标准流特性摆放,没有边偏移,很少用relative相对定位,相对自身原有位置移动,原有位置继续占有(不脱标…...
C高级Linux指令和shell脚本
XMind...
449. 序列化和反序列化二叉搜索树
难度:中等 昨天忘记做了。。。 简单学习一下官方题解 主要是:’ .join(map(str, arr)) int数组转String,中间有空格隔开 list(map(int, data.split())) String转int数组 class Codec:def serialize(self, root: TreeNode) -> str:arr […...
DockerCompose部署es和kibana
DockerCompose文件 version: 3.1 services:elasticsearch:image: elasticsearch:7.13.3container_name: elasticsearchprivileged: trueports:- "9200:9200"- "9300:9300"environment:- ES_JAVA_OPTS-Xms128m -Xmx1024m #设置使用jvm内存大小- cluster.na…...
windows系统docker中将vue项目网站部署在nginx上
一、首先在windows系统上下载并安装docker,要下载windows版本 https://www.docker.com/products/docker-desktop/ PS:安装过程中需要WSL,我的是win11系统,直接提示了我安装就可以下一步了。其他windows系统版本我不知道是否需要单…...
LabVIEW利用纳米结构干电极控制神经肌肉活动
LabVIEW利用纳米结构干电极控制神经肌肉活动 随着人口老龄化,长期护理的必要性变得更加重要,医疗中心的压力开始达到惊人的水平。全球对所有社会和经济部门的认识对于更好地协调卫生和社会服务之间的护理以及为更多的院外治疗提供条件至关重要。 关于医…...
使用PHPStudy在本地快速建立网站并实现局域网外访问(无公网IP)
文章目录 使用工具1. 本地搭建web网站1.1 下载phpstudy后解压并安装1.2 打开默认站点,测试1.3 下载静态演示站点1.4 打开站点根目录1.5 复制演示站点到站网根目录1.6 在浏览器中,查看演示效果。 2. 将本地web网站发布到公网2.1 安装cpolar内网穿透2.2 映…...
Java工具类--http请求-post
支持各类型报文与参数说明 说明: url : 地址timeout:超时时间 如3秒 3*1000contentType:类型 如 application/x-www-form-urlencoded application/jsonapplication/xmlrequestBody:报文内容 如 application/x-www-form-urlenco…...
HTTP【总结】
1. 当用户在浏览器输入网址回车之后,网络协议都做了哪些工作? 首先解析出URL中的域名,根据域名获取对应的ip地址,从浏览器缓存中查看,如果没有则从本机域名解析文件hosts中查看,还没有则从DNS的层层解析。…...
统计子岛屿
统计子岛屿 关于岛屿的相似题目: 岛屿数量 – 二维矩阵的dfs算法封闭岛屿数量 – 二维矩阵的dfs算法统计封闭岛屿的数目统计子岛屿不同岛屿的数量 class CountSubIslands:"""floodFill 算法1254. 统计子岛屿https://leetcode.cn/problems/count-su…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...
相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)
目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 (1)输入单引号 (2)万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...
【C++】纯虚函数类外可以写实现吗?
1. 答案 先说答案,可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...
Ubuntu系统复制(U盘-电脑硬盘)
所需环境 电脑自带硬盘:1块 (1T) U盘1:Ubuntu系统引导盘(用于“U盘2”复制到“电脑自带硬盘”) U盘2:Ubuntu系统盘(1T,用于被复制) !!!建议“电脑…...
在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南
在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南 背景介绍完整操作步骤1. 创建Docker容器环境2. 验证GUI显示功能3. 安装ROS Noetic4. 配置环境变量5. 创建ROS节点(小球运动模拟)6. 配置RVIZ默认视图7. 创建启动脚本8. 运行可视化系统效果展示与交互技术解析ROS节点通…...
