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…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
为什么要创建 Vue 实例
核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...
【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error
在前端开发中,JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作(如 Promise、async/await 等),开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝(r…...
区块链技术概述
区块链技术是一种去中心化、分布式账本技术,通过密码学、共识机制和智能合约等核心组件,实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点:数据存储在网络中的多个节点(计算机),而非…...
Sklearn 机器学习 缺失值处理 获取填充失值的统计值
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...
论文阅读:Matting by Generation
今天介绍一篇关于 matting 抠图的文章,抠图也算是计算机视觉里面非常经典的一个任务了。从早期的经典算法到如今的深度学习算法,已经有很多的工作和这个任务相关。这两年 diffusion 模型很火,大家又开始用 diffusion 模型做各种 CV 任务了&am…...
倒装芯片凸点成型工艺
UBM(Under Bump Metallization)与Bump(焊球)形成工艺流程。我们可以将整张流程图分为三大阶段来理解: 🔧 一、UBM(Under Bump Metallization)工艺流程(黄色区域ÿ…...
leetcode_69.x的平方根
题目如下 : 看到题 ,我们最原始的想法就是暴力解决: for(long long i 0;i<INT_MAX;i){if(i*ix){return i;}else if((i*i>x)&&((i-1)*(i-1)<x)){return i-1;}}我们直接开始遍历,我们是整数的平方根,所以我们分两…...
