蓝桥杯-最优清零方案

@toc

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个值最小的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的