当前位置: 首页 > 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…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...