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

http://www.lryc.cn/news/33792.html

相关文章:

  • Mac免费软件下载网站推荐(最全免费,替代MacWk)
  • GPU是什么
  • 20230305学习计划
  • SocketCan 应用编程
  • 从零学习python - 04函数方法与返回值
  • MySQL实战之事务到底是隔离的还是不隔离的
  • Elasticsearch:理解 Master,Elections,Quorum 及 脑裂
  • 【致敬女神】HTMLReport应用之Unittest+Python+Selenium+HTMLReport项目自动化测试实战
  • JAVA的16 个实用代码优化小技巧
  • 并发编程的三大挑战之原子性及其解决方案
  • QML动画(其他的动画)
  • Spark 配置项
  • 掌握Vue3模板语法,助你轻松实现高效Web开发
  • Jmeter+Ant+Jenkins接口自动化测试平台搭建
  • ncnn部署(CMakelists.txt)
  • SQL分库分表
  • 大数据分析案例-基于逻辑回归算法构建微博评论情感分类模型
  • 0105深度优先搜索算法非递归2种实现对比-无向图-数据结构和算法(Java)
  • 传统手工数据采集耗时耗力?Smartbi数据填报实现数据收集分析自动化
  • 《Spring源码深度分析》第5章 Bean的加载
  • 华为OD机试真题Java实现【求最大数字】真题+解题思路+代码(20222023)
  • Java——异常机制
  • 【大数据实时数据同步】超级详细的生产环境OGG(GoldenGate)12.2实时异构同步Oracle数据部署方案(下)
  • ESP32设备驱动-土壤湿度传感器驱动
  • 公网远程连接MongoDB数据库【内网穿透】
  • SQL注入——floor报错注入
  • P6入门:在EPS下创建项目(P6Professional)
  • Linux安装及管理应用和账号和权限管理 讲解
  • 【JDK1.8 新特性】Stream API
  • Springboot Maven打包跳过测试的五种方式总结 -Dmaven.test.skip=true