Acwing算法心得——街灯（差分）

大家好，我是晴天学长，差分广泛用于一段范围的加减运算，可以优化时间复杂度，需要的小伙伴请自取哦！如果觉得写的不错的话，可以点个关注哦，后续会继续更新的。💪💪💪

---

1 ）街灯

---

2) .算法思路

街灯
1.创建1010大小的数组
2.接受数据，注意数组的重置
3.差分加数，前缀和复原
4.开始遍历数组
无照亮范围统计量c
为0时，c++
不为0时
res+=c/2k+1，向上取整
5.注意遍历到n+1，所以数组的n+1要赋值为1，这样结尾那段也就可以统计上。

---

3) .算法步骤

1.创建一个大小为1010的一维数组a，用于存储每个位置的状态。
2.使用Scanner类从标准输入读取数据，进入一个while循环，直到没有更多的输入。
在循环内部，首先通过Arrays.fill方法将数组a的所有元素重置为0。
3.读取三个整数N、M和k，分别表示矩阵的行数、列数和现代艺术作品的数量。
使用一个循环读取M个现代艺术作品的位置，对应的数组元素进行更新。对于每个位置x，计算左边界l和右边界r，然后将a[l]加1，a[r+1]减1。
4.进行前缀和复原的操作，通过一个循环遍历数组a，每个位置的值加上前一个位置的值，即得到前缀和。
5.统计满足条件的现代艺术作品数量。遍历数组a，如果当前位置的值大于0，则将累计值c除以len（2k+1）并向上取整，加到结果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）.总结

• 差分的应用。
• 数组的越界问题。

---

试题链接：