蓝桥杯-最优清零方案(2022省赛)
蓝桥杯-最优清零方案
- 1、问题描述
- 2、解题思路
- 3、代码实现
1、问题描述
给定一个长度为 N 的数列 1,2,⋯,A1,A2,...,ANA_1,A_2,...,A_NA1,A2,...,AN 。现在小蓝想通过若干次操作将 这个数列中每个数字清零。
每次操作小蓝可以选择以下两种之一:
1. 选择一个大于 0 的整数, 将它减去 1 ;
2. 选择连续 K 个大于 0 的整数, 将它们各减去 1 。
小蓝最少经过几次操作可以将整个数列清零?
输入格式
输入第一行包含两个整数 N* 和 K* 。
第二行包含 N 个整数 1,2,⋯,A1,A2,...,ANA_1,A_2,...,A_NA1,A2,...,AN 。
输出格式
输出一个整数表示答案。
样例输入
4 2
1 2 3 4
样例输出
6
评测用例规模与约定
对于 20% 的评测用例,1≤K≤N≤10 。
对于 40% 的评测用例, 1≤K≤N≤100 。
对于 50% 的评测用例, 1≤K≤N≤1000 。
对于 60% 的评测用例, 1≤K≤N≤10000 。
对于 70% 的评测用例, 1≤K≤N≤100000 。
对于所有评测用例, 1≤K≤N≤1000000,0≤AiA_iAi≤1000000 。
运行限制
- 最大运行时间:15s
- 最大运行内存: 512M
2、解题思路
题中给了两个操作,操作1是一次只能减1,操作2可以将连续K个数字同时减1,所以我们的目标其实是看能执行多少次操作2,操作2执行完之后,数组中将会剩下不连续的数字,这些数字只能执行操作1,所以我们直接将剩下这些数字相加即可。
利用滑动窗口思想,先设置一个计数器count=0,令m=0通过一个while (m<=arr.length-k)循环来控制滑动窗口,每次开始的时候找到k个连续区间内最小的值min和该数字对应的下标index,然后让这个区间内的所有制都减去min,此时给修改计数器count+=min(其实就是一次性执行了很多次操作2)。
由于此时下标为index位置处的数字已经为零了,我们直接将下一次窗口的左指针移动到index的下一个位置,也就是令m=index+1,这样子可以减少很多重复的判断。
当while循环结束的时候,说明此时数组中已经没有连续k个大于0的整数区间了,接下来数组中的所有操作都只能执行操作1,一个个减太慢,直接对当前数组中的所有元素求和,即sum = Arrays.stream(arr).sum();可以统计所有操作1的执行次数。
最终的总执行次数为操作2的执行次数(滑动窗口中的count)+操作1的执行次数
3、代码实现
package LanQiaoBei.最优清零方案;import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();int k = scan.nextInt();long[] arr = new long[n];for (int i = 0; i <arr.length; i++) {arr[i]=scan.nextLong();}System.out.println(process(arr, k));}/*** 计数器count=0* 其实主要是看最多能进行几次操作2,利用滑动窗口,每次找到k长度区间内的最小值min,* 如果该区间内的数字都是K个大于0的整数,那就让该区间的所有值都减去这个最小值min,计数改变count+min* 滑动窗口执行结束之后,此时已经没有连续k个大于0的整数区间了,接下来要对剩下的所有数组进行减1的操作,为了方便* 这里直接对数组中的所有元素求和即可,最后结果为count+sum(arr)*/public static long process(long[] arr,int k){long count=0;int m=0;while (m<=arr.length-k) {long min=Integer.MAX_VALUE;int index=-1;for (int i = m; i <m+k ; i++) {//找到k个值最小的indexif(arr[i]<=min){min=arr[i];index=i;}}//区间内所有的值减去minfor (int i = m; i <m+k ; i++) {arr[i]-=min;}count+=min; //计数m=index+1; //索引掉到先置0的右边索引}//循环结束之后,已经没有连续k个不为零的区间了,直接将数组元素求和就是减1的次数long sum = Arrays.stream(arr).sum();count+=sum;return count;}
}
跑一个测试用例看看:

这个代码是可以AC的
思路来源于这位大佬:https://www.lanqiao.cn/questions/319168/
相关文章:
蓝桥杯-最优清零方案(2022省赛)
蓝桥杯-最优清零方案1、问题描述2、解题思路3、代码实现1、问题描述 给定一个长度为 N 的数列 1,2,⋯,A1,A2,...,ANA_1,A_2,...,A_NA1,A2,...,AN 。现在小蓝想通过若干次操作将 这个数列中每个数字清零。 每次操作小蓝可以选择以下两种之一: 1. 选择一个大于 0 的整数, 将…...
Mac免费软件下载网站推荐(最全免费,替代MacWk)
一、Appstorrent 官方网站: https://appstorrent.ru/ 这是一个俄语网站,其他很多网站资源都来自这里。点击右上角切换到中文。不需要登录网站,直接从软件详情页下载即可。体验非常好。 二、Xclient 官方网站: https://xclie…...
GPU是什么
近期ChatGPT十分火爆,随之而来的是M国开始禁售高端GPU显卡。M国想通过禁售GPU显卡的方式阻挡中国在AI领域的发展。 GPU是什么?GPU(英语:Graphics Processing Unit,缩写:GPU)是显卡的“大脑”&am…...
20230305学习计划
目录 第二天学习开发框架 前言 一、巩固复习第一天20230304学习笔记 二、SpringMVC中的控制器是不是单例模式?如果是,如何保证线程安全? 1、控制器是单例模式,是线程不安全的。 2、Spring中保证线程安全的方法: …...
SocketCan 应用编程
SocketCan 应用编程 由于 Linux 系统将 CAN 设备作为网络设备进行管理,因此在 CAN 总线应用开发方面,Linux 提供了SocketCAN 应用编程接口,使得 CAN 总线通信近似于和以太网的通信,应用程序开发接口更加通用,也更加灵…...
从零学习python - 04函数方法与返回值
函数:Function-也称为方法,是组织好的、可重复使用的,用来实现指定功能的代码块。函数的定义与调用:创建函数目的是封装业务逻辑,实现代码复用# 创建函数关键字:def(definition)def fun1(x, y):print(x y)函数的参数:python函数中…...
MySQL实战之事务到底是隔离的还是不隔离的
1.前言 我们在MySQL实战之事务隔离:为什么你改了我还看不见讲过事务隔离级别的时候提到过,如果是可重复读隔离级别,事务T启动的时候会创建一个视图read-view,之后事务T执行期间,即使有其他事务修改了数据,事务T看到的…...
Elasticsearch:理解 Master,Elections,Quorum 及 脑裂
集群中的每个节点都可以分配多个角色:master、data、ingest、ml(机器学习)等。 我们在当前讨论中感兴趣的角色之一是 master 角色。 在 Elasticsearch 的配置中,我们可以配置一个节点为 master 节点。master 角色的分配表明该节点…...
【致敬女神】HTMLReport应用之Unittest+Python+Selenium+HTMLReport项目自动化测试实战
HTMLReport应用之UnittestPythonSeleniumHTMLReport项目自动化测试实战1 测试框架结构2 技术栈3 实现思路3.1 使用HtmlTestRunner3.2 使用HTMLReport4 TestRunner参数说明4.1 源码4.2 参数说明5 框架代码5.1 common/reportOut.py5.2 common/sendMain.py5.3 report5.3.1 xxx.htm…...
JAVA的16 个实用代码优化小技巧
一、类成员与方法的可见性最小化 举例:如果是一个private的方法,想删除就删除。 如果一个public的service方法,或者一个public的成员变量,删除一下,不得思考很多。 二、使用位移操作替代乘除法 计算机是使用二进制…...
并发编程的三大挑战之原子性及其解决方案
目录 一、原子性问题 1、带来原子性问题的原因 2、如何解决线程切换带来的原子问题 2.1、使用synchronized关键字来保证 2.2、使用CAS来保证原子性 2.3、使用lock锁来保证 一、原子性问题 1、带来原子性问题的原因 线程切换是带来原子的根本原因,java的并发程…...
QML动画(其他的动画)
PauseAnimation (暂停动画) 为动画提供暂停 Rectangle{id:rect1width: 100;height: 100;x:100;y:100color: "lightBlue"SequentialAnimation{running: trueColorAnimation {target: rect1;property: "color";…...
Spark 配置项
Spark 配置项硬件资源类CPU内存堆外内User Memory/Spark 可用内存Execution/Storage Memory磁盘ShuffleSpark SQLJoin 策略调整自动分区合并自动倾斜处理配置项分为 3 类: 硬件资源类 : 与 CPU、内存、磁盘有关的配置项Shuffle 类 : Shuffle 计算过程的配置项Spark SQL : Spar…...
掌握Vue3模板语法,助你轻松实现高效Web开发
Vue3作为前端开发中的一种主流框架,为我们提供了多种灵活的方式来处理模板语法。除了基础的模板语法,Vue3还提供了一些高级的语法,可以让我们更好地处理组件、响应式数据和UI逻辑等。在这篇博客中,我们将介绍Vue3中的一些高级模板…...
Jmeter+Ant+Jenkins接口自动化测试平台搭建
平台简介一个完整的接口自动化测试平台需要支持接口的自动执行,自动生成测试报告,以及持续集成。Jmeter支持接口的测试,Ant支持自动构建,而Jenkins支持持续集成,所以三者组合在一起可以构成一个功能完善的接口自动化测…...
ncnn部署(CMakelists.txt)
1. NCNN 环境安装 参考博客: 基于ncnn的yolov5模型部署 1. 1 protobuf编译 打开VS2013/VS2019的X64命令行(注意不是cmd),我这里以V32013环境进行编译 > cd <protobuf-root-dir> > mkdir build-vs2013 > cd build-vs2013 > cmake -G"NMake Makefil…...
SQL分库分表
什么是分库分表? 分库分表是两种操作,一种是分库,一种是分表。 分库分表又分为垂直拆分和水平拆分两种。 (1)分库:将原来存放在单个数据库中的数据,拆分到多个数据库中存放。 (2&…...
大数据分析案例-基于逻辑回归算法构建微博评论情感分类模型
🤵♂️ 个人主页:@艾派森的个人主页 ✍🏻作者简介:Python学习者 🐋 希望大家多多支持,我们一起进步!😄 如果文章对你有帮助的话, 欢迎评论 💬点赞👍🏻 收藏 📂加关注+ 喜欢大数据分析项目的小伙伴,希望可以多多支持该系列的其他文章 大数据分析案例合集…...
0105深度优先搜索算法非递归2种实现对比-无向图-数据结构和算法(Java)
1 两种非递归实现 在前面我们解决无向图的单点通性和单点路径问题时,都用到了深度优先搜索算法。深度优先搜索算法可以用递归和非递归两种方式。这里讨论非递归实现。 无向图结构使用邻接表实现。 第一种非递归方法(推荐),代码如…...
传统手工数据采集耗时耗力?Smartbi数据填报实现数据收集分析自动化
企业在日常经营管理过程中,往往需要收集很多内外部的信息,清洗整理后再进行存储、分析、呈现、决策支持等各种作业,如何高效收集结构化数据是企业管理者经常要面对的问题。传统手工的数据采集方式不仅耗费了大量人力时间成本,还容…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
10-Oracle 23 ai Vector Search 概述和参数
一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...
回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
Ubuntu系统复制(U盘-电脑硬盘)
所需环境 电脑自带硬盘:1块 (1T) U盘1:Ubuntu系统引导盘(用于“U盘2”复制到“电脑自带硬盘”) U盘2:Ubuntu系统盘(1T,用于被复制) !!!建议“电脑…...
JavaScript 标签加载
目录 JavaScript 标签加载script 标签的 async 和 defer 属性,分别代表什么,有什么区别1. 普通 script 标签2. async 属性3. defer 属性4. type"module"5. 各种加载方式的对比6. 使用建议 JavaScript 标签加载 script 标签的 async 和 defer …...
