当前位置：首页 > article >正文

差分数组的使用

article 2024/12/22 3:31:54

这个问题要求我们通过杨学长的超能力来在一条马路上种树，并计算最终种树的总长度。每次杨学长的超能力作用会覆盖一个区间，我们需要计算最终种树的总长度。

问题分析

给定一个马路长度为 n，有 m 次操作，每次操作会让某个区间 [l, r] 种上树。我们的任务是求出所有操作后，马路上最终种树的总长度（即被种树的区域的长度）。

思路

直接模拟每次操作：我们可以用一个布尔数组 tree[n] 来记录马路上每个位置是否被种树。每次操作时，将该区间内的所有位置标记为种树。
优化的思路：直接模拟每次操作会导致时间复杂度较高，尤其是当区间 [l, r] 很长时。因此，我们可以考虑使用 区间标记法，即使用一个辅助数组来记录区间的变化（类似差分数组），然后通过一次遍历得到最终结果。

优化方案

使用一个大小为 n + 1 的数组 tree 来记录每个位置是否种树。
对于每次操作 (l, r)，我们可以：
- 在 tree[l] 位置标记种树的开始（将 tree[l] 设置为 1）。
- 在 tree[r + 1] 位置标记种树的结束（将 tree[r + 1] 设置为 -1，表示从 r + 1 开始就不再种树）。
最后我们通过一次遍历累加这个差分数组，计算哪些位置最终种了树。

代码实现

#include <stdio.h>

#define MAX_N 1000000

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    // 创建一个差分数组，初始值为 0
    int tree[MAX_N + 2] = {0};  // +2 是为了防止访问 tree[r + 1] 时越界
    
    // 处理每一个操作
    for (int i = 0; i < m; i++) {
        int l, r;
        scanf("%d %d", &l, &r);
        tree[l] += 1;        // 从 l 开始种树
        tree[r + 1] -= 1;    // 从 r+1 停止种树
    }
    
    // 统计最终种树的总长度
    int count = 0;
    int current = 0; // 当前的种树标记
    for (int i = 1; i <= n; i++) {
        current += tree[i];  // 更新当前标记
        if (current > 0) {   // 如果当前标记大于 0，表示这个位置种了树
            count++;
        }
    }
    
    // 输出结果
    printf("%d\n", count);
    
    return 0;
}

解释

输入处理：
- 通过 scanf 读取 n 和 m，其中 n 是马路的长度，m 是操作次数。
- 接着，读取每次操作的区间 [l, r]。
差分数组处理：
- 初始化一个大小为 n + 2 的数组 tree（多一个位置防止 r + 1 越界）。
- 对于每个操作 (l, r)，更新差分数组：
  - tree[l] += 1 表示从位置 l 开始种树。
  - tree[r + 1] -= 1 表示从位置 r + 1 开始停止种树。
统计种树的长度：
- 初始化一个变量 current 来记录当前位置是否种树。
- 遍历 tree 数组，通过累加差分值来计算当前位置是否种树，如果是种树，增加种树长度的计数。
输出：
- 最后输出种树的总长度。