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

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算法心得——街灯(差分)

大家好&#xff0c;我是晴天学长&#xff0c;差分广泛用于一段范围的加减运算&#xff0c;可以优化时间复杂度&#xff0c;需要的小伙伴请自取哦&#xff01;如果觉得写的不错的话&#xff0c;可以点个关注哦&#xff0c;后续会继续更新的。&#x1f4aa;&#x1f4aa;&#x1…...

streamlit执行报错WARNING,重新安装碰到问题如何解决

streamlit执行报错WARNING&#xff0c;重新安装碰到问题如何解决 如何解决1、卸载已经安装的程序2、再次安装程序3、出现如下yinstaller 警告问题&#xff1a;4、又出现“which is not on PATH”警告。5、解决方案 发现在安装的时候有很多WARNING出现&#xff0c;但是没有但回事…...

《C++设计模式》——行为型

前言 行为型模式是对在不同的对象之间划分责任和算法的抽象化。行为型模式不仅仅关注类和对象的结构&#xff0c;而且重点关注它们之间的相互作用。 Interpreter(解释器) Template Method(模板方法) GOOD&#xff1a;把不变的代码部分都转移到父类中&#xff0c;将可变的代…...

什么是原生IP?原生IP与住宅IP有何区别?

相信许多做跨境的都会接触到IP代理&#xff0c;比如电商平台、社媒平台、收款平台等等&#xff0c;都会检测IP。那也会经常听到一些词汇&#xff1a;原生IP、住宅IP&#xff0c;这两者之间有什么区别呢&#xff1f;什么业务需要用到呢&#xff1f;接下来带大家具体了解一下。 什…...

element-plus 表格-自定义样式实现

效果如下 代码如下 <template><h2>表格自定义样式</h2><div style"background-color: cadetblue; height: 600px;"><div class"regulaContainer"><el-table ref"tableRef" :data"tableData" border …...

MVCC

MVCC&#xff08;Multi-Version Concurrency Control&#xff09;是数据库管理系统&#xff08;DBMS&#xff09;中的一种技术&#xff0c;用于管理并发访问数据&#xff0c;允许多个事务同时进行而不互相干扰&#xff0c;同时保持数据的一致性。 MVCC 的工作原理如下&#xf…...

你不知道的JavaScript---对象

1.语法 对象可以通过两种方式定义&#xff1a;一种是对象字面量形式&#xff0c;一种是构造形式 对象字面量&#xff1a; var muObject {key: value }构造形式的&#xff1a; var myObject new Object() myObject.key value不管是使用对象字面量形式还是构造形式创建出来…...

C++项目实战——基于多设计模式下的同步异步日志系统-①-项目介绍

文章目录 专栏导读项目介绍开发环境核心技术环境搭建日志系统介绍1.为什么需要日志系统2.日志系统技术实现2.1同步写日志2.2异步写日志 专栏导读 &#x1f338;作者简介&#xff1a;花想云 &#xff0c;在读本科生一枚&#xff0c;C/C领域新星创作者&#xff0c;新星计划导师&a…...

解决Oracle数据库中日期格式不识别的问题

在数据库开发中&#xff0c;我们经常需要处理日期和时间数据。当我们在Oracle数据库中执行UPDATE语句时&#xff0c;可能会遇到ORA-01821错误&#xff0c;该错误表示提供的日期格式无法被数据库识别。本文将介绍如何解决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老师前端)定位

定位可以让盒子自由的在某个盒子内移动位置或者固定在屏幕中某个位置&#xff0c;并且可以压住其他盒子。 定位 定位模式 边偏移 定位模式说明static静态定位,按标准流特性摆放,没有边偏移,很少用relative相对定位,相对自身原有位置移动,原有位置继续占有&#xff08;不脱标…...

C高级Linux指令和shell脚本

XMind...

449. 序列化和反序列化二叉搜索树

难度&#xff1a;中等 昨天忘记做了。。。 简单学习一下官方题解 主要是&#xff1a;’ .join(map(str, arr)) int数组转String&#xff0c;中间有空格隔开 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&#xff0c;要下载windows版本 https://www.docker.com/products/docker-desktop/ PS&#xff1a;安装过程中需要WSL&#xff0c;我的是win11系统&#xff0c;直接提示了我安装就可以下一步了。其他windows系统版本我不知道是否需要单…...

LabVIEW利用纳米结构干电极控制神经肌肉活动

LabVIEW利用纳米结构干电极控制神经肌肉活动 随着人口老龄化&#xff0c;长期护理的必要性变得更加重要&#xff0c;医疗中心的压力开始达到惊人的水平。全球对所有社会和经济部门的认识对于更好地协调卫生和社会服务之间的护理以及为更多的院外治疗提供条件至关重要。 关于医…...

使用PHPStudy在本地快速建立网站并实现局域网外访问(无公网IP)

文章目录 使用工具1. 本地搭建web网站1.1 下载phpstudy后解压并安装1.2 打开默认站点&#xff0c;测试1.3 下载静态演示站点1.4 打开站点根目录1.5 复制演示站点到站网根目录1.6 在浏览器中&#xff0c;查看演示效果。 2. 将本地web网站发布到公网2.1 安装cpolar内网穿透2.2 映…...

Java工具类--http请求-post

支持各类型报文与参数说明 说明&#xff1a; url : 地址timeout&#xff1a;超时时间 如3秒 3*1000contentType&#xff1a;类型 如 application/x-www-form-urlencoded application/jsonapplication/xmlrequestBody&#xff1a;报文内容 如 application/x-www-form-urlenco…...

HTTP【总结】

1. 当用户在浏览器输入网址回车之后&#xff0c;网络协议都做了哪些工作&#xff1f; 首先解析出URL中的域名&#xff0c;根据域名获取对应的ip地址&#xff0c;从浏览器缓存中查看&#xff0c;如果没有则从本机域名解析文件hosts中查看&#xff0c;还没有则从DNS的层层解析。…...

统计子岛屿

统计子岛屿 关于岛屿的相似题目&#xff1a; 岛屿数量 – 二维矩阵的dfs算法封闭岛屿数量 – 二维矩阵的dfs算法统计封闭岛屿的数目统计子岛屿不同岛屿的数量 class CountSubIslands:"""floodFill 算法1254. 统计子岛屿https://leetcode.cn/problems/count-su…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...