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

蓝桥杯-最优清零方案(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≤KN≤10 。

  对于 40% 的评测用例, 1≤KN≤100 。

  对于 50% 的评测用例, 1≤KN≤1000 。

  对于 60% 的评测用例, 1≤KN≤10000 。

  对于 70% 的评测用例, 1≤KN≤100000 。

  对于所有评测用例, 1≤KN≤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;}
}

跑一个测试用例看看:

image-20230307222415464

   这个代码是可以AC的

image-20230307222447115

思路来源于这位大佬: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 官方网站&#xff1a; https://appstorrent.ru/ 这是一个俄语网站&#xff0c;其他很多网站资源都来自这里。点击右上角切换到中文。不需要登录网站&#xff0c;直接从软件详情页下载即可。体验非常好。 二、Xclient 官方网站&#xff1a; https://xclie…...

GPU是什么

近期ChatGPT十分火爆&#xff0c;随之而来的是M国开始禁售高端GPU显卡。M国想通过禁售GPU显卡的方式阻挡中国在AI领域的发展。 GPU是什么&#xff1f;GPU&#xff08;英语&#xff1a;Graphics Processing Unit&#xff0c;缩写&#xff1a;GPU&#xff09;是显卡的“大脑”&am…...

20230305学习计划

目录 第二天学习开发框架 前言 一、巩固复习第一天20230304学习笔记 二、SpringMVC中的控制器是不是单例模式&#xff1f;如果是&#xff0c;如何保证线程安全&#xff1f; 1、控制器是单例模式&#xff0c;是线程不安全的。 2、Spring中保证线程安全的方法&#xff1a; …...

SocketCan 应用编程

SocketCan 应用编程 由于 Linux 系统将 CAN 设备作为网络设备进行管理&#xff0c;因此在 CAN 总线应用开发方面&#xff0c;Linux 提供了SocketCAN 应用编程接口&#xff0c;使得 CAN 总线通信近似于和以太网的通信&#xff0c;应用程序开发接口更加通用&#xff0c;也更加灵…...

从零学习python - 04函数方法与返回值

函数&#xff1a;Function-也称为方法&#xff0c;是组织好的、可重复使用的&#xff0c;用来实现指定功能的代码块。函数的定义与调用:创建函数目的是封装业务逻辑&#xff0c;实现代码复用# 创建函数关键字:def(definition)def fun1(x, y):print(x y)函数的参数:python函数中…...

MySQL实战之事务到底是隔离的还是不隔离的

1.前言 我们在MySQL实战之事务隔离&#xff1a;为什么你改了我还看不见讲过事务隔离级别的时候提到过&#xff0c;如果是可重复读隔离级别&#xff0c;事务T启动的时候会创建一个视图read-view,之后事务T执行期间&#xff0c;即使有其他事务修改了数据&#xff0c;事务T看到的…...

Elasticsearch:理解 Master,Elections,Quorum 及 脑裂

集群中的每个节点都可以分配多个角色&#xff1a;master、data、ingest、ml&#xff08;机器学习&#xff09;等。 我们在当前讨论中感兴趣的角色之一是 master 角色。 在 Elasticsearch 的配置中&#xff0c;我们可以配置一个节点为 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 个实用代码优化小技巧

一、类成员与方法的可见性最小化 举例&#xff1a;如果是一个private的方法&#xff0c;想删除就删除。 如果一个public的service方法&#xff0c;或者一个public的成员变量&#xff0c;删除一下&#xff0c;不得思考很多。 二、使用位移操作替代乘除法 计算机是使用二进制…...

并发编程的三大挑战之原子性及其解决方案

目录 一、原子性问题 1、带来原子性问题的原因 2、如何解决线程切换带来的原子问题 2.1、使用synchronized关键字来保证 2.2、使用CAS来保证原子性 2.3、使用lock锁来保证 一、原子性问题 1、带来原子性问题的原因 线程切换是带来原子的根本原因&#xff0c;java的并发程…...

QML动画(其他的动画)

PauseAnimation &#xff08;暂停动画&#xff09; 为动画提供暂停 Rectangle{id:rect1width: 100;height: 100;x:100;y:100color: "lightBlue"SequentialAnimation{running: trueColorAnimation {target: rect1&#xff1b;property: "color"&#xff1b;…...

Spark 配置项

Spark 配置项硬件资源类CPU内存堆外内User Memory/Spark 可用内存Execution/Storage Memory磁盘ShuffleSpark SQLJoin 策略调整自动分区合并自动倾斜处理配置项分为 3 类: 硬件资源类 : 与 CPU、内存、磁盘有关的配置项Shuffle 类 : Shuffle 计算过程的配置项Spark SQL : Spar…...

掌握Vue3模板语法,助你轻松实现高效Web开发

Vue3作为前端开发中的一种主流框架&#xff0c;为我们提供了多种灵活的方式来处理模板语法。除了基础的模板语法&#xff0c;Vue3还提供了一些高级的语法&#xff0c;可以让我们更好地处理组件、响应式数据和UI逻辑等。在这篇博客中&#xff0c;我们将介绍Vue3中的一些高级模板…...

Jmeter+Ant+Jenkins接口自动化测试平台搭建

平台简介一个完整的接口自动化测试平台需要支持接口的自动执行&#xff0c;自动生成测试报告&#xff0c;以及持续集成。Jmeter支持接口的测试&#xff0c;Ant支持自动构建&#xff0c;而Jenkins支持持续集成&#xff0c;所以三者组合在一起可以构成一个功能完善的接口自动化测…...

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分库分表

什么是分库分表&#xff1f; 分库分表是两种操作&#xff0c;一种是分库&#xff0c;一种是分表。 分库分表又分为垂直拆分和水平拆分两种。 &#xff08;1&#xff09;分库&#xff1a;将原来存放在单个数据库中的数据&#xff0c;拆分到多个数据库中存放。 &#xff08;2&…...

大数据分析案例-基于逻辑回归算法构建微博评论情感分类模型

🤵‍♂️ 个人主页:@艾派森的个人主页 ✍🏻作者简介:Python学习者 🐋 希望大家多多支持,我们一起进步!😄 如果文章对你有帮助的话, 欢迎评论 💬点赞👍🏻 收藏 📂加关注+ 喜欢大数据分析项目的小伙伴,希望可以多多支持该系列的其他文章 大数据分析案例合集…...

0105深度优先搜索算法非递归2种实现对比-无向图-数据结构和算法(Java)

1 两种非递归实现 在前面我们解决无向图的单点通性和单点路径问题时&#xff0c;都用到了深度优先搜索算法。深度优先搜索算法可以用递归和非递归两种方式。这里讨论非递归实现。 无向图结构使用邻接表实现。 第一种非递归方法&#xff08;推荐&#xff09;&#xff0c;代码如…...

传统手工数据采集耗时耗力?Smartbi数据填报实现数据收集分析自动化

企业在日常经营管理过程中&#xff0c;往往需要收集很多内外部的信息&#xff0c;清洗整理后再进行存储、分析、呈现、决策支持等各种作业&#xff0c;如何高效收集结构化数据是企业管理者经常要面对的问题。传统手工的数据采集方式不仅耗费了大量人力时间成本&#xff0c;还容…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...