网站建设对付客户,网络销售怎么跟客户聊天,莆田建设银行官方网站,网站建设 天佩营销蓝桥杯-最优清零方案1、问题描述2、解题思路3、代码实现1、问题描述 给定一个长度为 N 的数列 1,2,⋯,A1,A2,...,ANA_1,A_2,...,A_NA1,A2,...,AN 。现在小蓝想通过若干次操作将 这个数列中每个数字清零。 每次操作小蓝可以选择以下两种之一: 1. 选择一个大于 0 的整数, 将…
蓝桥杯-最优清零方案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≤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≤AiA_iAi≤1000000 。
运行限制
最大运行时间15s最大运行内存: 512M
2、解题思路 题中给了两个操作操作1是一次只能减1操作2可以将连续K个数字同时减1所以我们的目标其实是看能执行多少次操作2操作2执行完之后数组中将会剩下不连续的数字这些数字只能执行操作1所以我们直接将剩下这些数字相加即可。 利用滑动窗口思想先设置一个计数器count0令m0通过一个while (marr.length-k)循环来控制滑动窗口每次开始的时候找到k个连续区间内最小的值min和该数字对应的下标index然后让这个区间内的所有制都减去min此时给修改计数器countmin(其实就是一次性执行了很多次操作2)。 由于此时下标为index位置处的数字已经为零了我们直接将下一次窗口的左指针移动到index的下一个位置也就是令mindex1,这样子可以减少很多重复的判断。 当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));}/*** 计数器count0* 其实主要是看最多能进行几次操作2利用滑动窗口每次找到k长度区间内的最小值min* 如果该区间内的数字都是K个大于0的整数那就让该区间的所有值都减去这个最小值min计数改变countmin* 滑动窗口执行结束之后此时已经没有连续k个大于0的整数区间了接下来要对剩下的所有数组进行减1的操作为了方便* 这里直接对数组中的所有元素求和即可最后结果为countsum(arr)*/public static long process(long[] arr,int k){long count0;int m0;while (marr.length-k) {long minInteger.MAX_VALUE;int index-1;for (int i m; i mk ; i) {//找到k个值最小的indexif(arr[i]min){minarr[i];indexi;}}//区间内所有的值减去minfor (int i m; i mk ; i) {arr[i]-min;}countmin; //计数mindex1; //索引掉到先置0的右边索引}//循环结束之后已经没有连续k个不为零的区间了直接将数组元素求和就是减1的次数long sum Arrays.stream(arr).sum();countsum;return count;}
}
跑一个测试用例看看 这个代码是可以AC的 思路来源于这位大佬https://www.lanqiao.cn/questions/319168/
