江苏新站优化上海网络维护公司20强

1、问题描述

  给定一个长度为 N 的数列 1,2,⋯,$A_1,A_2,...,A_N$ 。现在小蓝想通过若干次操作将 这个数列中每个数字清零。

  每次操作小蓝可以选择以下两种之一:

  1. 选择一个大于 0 的整数, 将它减去 1 ;
  2. 选择连续 K 个大于 0 的整数, 将它们各减去 1 。

  小蓝最少经过几次操作可以将整个数列清零?

输入格式

  输入第一行包含两个整数 N* 和 K* 。

  第二行包含 N 个整数 1,2,⋯,$A_1,A_2,...,A_N$ 。

输出格式

  输出一个整数表示答案。

样例输入

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≤$A_i$≤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/