蓝桥杯2022年第十三届省赛真题-最优清零方案 java

在这里插入图片描述

样例输入、输出：

输入1：

4 2
1 2 3 4

输出1

输入2：

4 2
1 2 3 4

输出2

解法：

滑动窗口解法如下。主要思路就是：用长度为k的滑动窗口，每遇到连续k个不为0的数，记录这k个数中的最小值为min，序号为min_I，做min次连续减的操作，然后窗口移动到min_I + 1。

import java.util.Scanner;

public class Main {
	/**
	 * 思路：用长度为k的滑动窗口，每遇到连续k个不为0的数，
	 * 记录这k个数中的最小值为min，序号为min_I，做min次连续减的操作
	 * 然后窗口移动到min_I + 1
	 */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] nums = new int[n];

        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }

        long count = 0L;
        int i = 0;

        while (i <= n - k) {
        	// 连续k个数中的最小值及其序号
        	int min = nums[i + k - 1];
			int minI = i + k - 1;
            boolean hasZero = false;

            // 找到连续 k 个数中的最小值
            // 反向遍历，有0及时退出
            for(int j = i + k - 1; j >= i; j--) {
				if(nums[j] == 0) {
					hasZero = true;
					i = j + 1;
					break;
				}
				if(nums[j] < min) {
					min = nums[j];
					minI = j;
				}
			}

            // 窗口中没有0，则进行连续减操作
            if (!hasZero) {
                count += min;

                // 减去连续 k 个数中的最小值
                for (int j = i; j < i + k; j++) {
                    nums[j] -= min;
                }
                i = minI + 1;
            }
        }

        // 计算剩余数字的总和，即每次对一个数-1操作
        for (int num : nums) {
        	count += num;
        }

        System.out.println(count);
    }
}