蓝桥杯-最优清零方案(2022省赛)
蓝桥杯-最优清零方案
1、问题描述
给定一个长度为 N 的数列 1,2,⋯,
。现在小蓝想通过若干次操作将 这个数列中每个数字清零。
每次操作小蓝可以选择以下两种之一:
1. 选择一个大于 0 的整数, 将它减去 1 ; 2. 选择连续 K 个大于 0 的整数, 将它们各减去 1 。
小蓝最少经过几次操作可以将整个数列清零?
输入格式
输入第一行包含两个整数 N* 和 K* 。
第二行包含 N 个整数 1,2,⋯,
。
输出格式
输出一个整数表示答案。
样例输入
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≤
≤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个值最小的index
if(arr[i]<=min){
min=arr[i];
index=i;
}
}
//区间内所有的值减去min
for (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/