个人做收费网站,南京网站推广哪家便宜,wordpress导出静态网站,wordpress设计的网站大家好#xff0c;我是晴天学长#xff0c;差分广泛用于一段范围的加减运算#xff0c;可以优化时间复杂度#xff0c;需要的小伙伴请自取哦#xff01;如果觉得写的不错的话#xff0c;可以点个关注哦#xff0c;后续会继续更新的。#x1f4aa;#x1f4aa;#x1…大家好我是晴天学长差分广泛用于一段范围的加减运算可以优化时间复杂度需要的小伙伴请自取哦如果觉得写的不错的话可以点个关注哦后续会继续更新的。 1 街灯 2) .算法思路
街灯 1.创建1010大小的数组 2.接受数据注意数组的重置 3.差分加数前缀和复原 4.开始遍历数组 无照亮范围统计量c 为0时c 不为0时 resc/2k1向上取整 5.注意遍历到n1所以数组的n1要赋值为1这样结尾那段也就可以统计上。 3) .算法步骤
1.创建一个大小为1010的一维数组a用于存储每个位置的状态。 2.使用Scanner类从标准输入读取数据进入一个while循环直到没有更多的输入。 在循环内部首先通过Arrays.fill方法将数组a的所有元素重置为0。 3.读取三个整数N、M和k分别表示矩阵的行数、列数和现代艺术作品的数量。 使用一个循环读取M个现代艺术作品的位置对应的数组元素进行更新。对于每个位置x计算左边界l和右边界r然后将a[l]加1a[r1]减1。 4.进行前缀和复原的操作通过一个循环遍历数组a每个位置的值加上前一个位置的值即得到前缀和。 5.统计满足条件的现代艺术作品数量。遍历数组a如果当前位置的值大于0则将累计值c除以len2k1并向上取整加到结果res中并将c重置为0否则将c加1。 输出结果res。 3.代码示例
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;public class Main {static int[] a new int[1010];public static void main(String[] args) {Scanner scanner new Scanner(System.in);while (scanner.hasNext()) {//数组重置操作Arrays.fill(a, 0);int res 0;int N scanner.nextInt();int M scanner.nextInt();int k scanner.nextInt();//避免越界操作,跟着大佬操作从1开始.while (M-- 0) {int x scanner.nextInt();int l Math.max(1, x - k);int r Math.min(N, x k);a[l];a[r 1]--;}//前缀和复原for (int i 1; i N; i) {a[i] (a[i - 1]);}//统计操作double c 0;double len 2 * k 1;a[N 1] 1;for (int i 1; i N 1; i) {if (a[i] 0) {res Math.ceil(c / len);c 0;} else {c;}}System.out.println(res);}}
} 4.总结
差分的应用。数组的越界问题。 试题链接
