竞赛编程题排查：求覆盖画廊最少洒水器数量的代码问题

问题描述 #

一个摆放植物的画廊被划分为n个区域，编号为0、1、2…n-1。每个分区都支持安装洒水器，位于i分区、射程为x的洒水器可以浇灌所有处于i-x到i+x区间内的分区。给定长度为n的数组gallery[]，其中gallery[i]是i分区安装的洒水器射程（值为-1代表该位置未安装洒水器），请返回浇灌完整画廊需要开启的最少洒水器数量。如果现有洒水器无法覆盖整个画廊，返回-1。

原解题思路 #

• 创建频率数组，数组第i位存储可以浇灌画廊第i块区域的洒水器数量。
• 遍历所有洒水器后，如果频率数组中存在值为0的元素，直接返回-1，原因是即使开启全部洒水器也无法覆盖所有区域。
• 使用std::stable_sort将所有洒水器按照射程从小到大排序。
• 从射程最小的洒水器开始遍历，移除冗余的洒水器。

原代码实现 #

typedef struct sprinkler {
    int l;
    int r;
} sprinkler;

int min_sprinklers(int gallery[], int n)
{
    int freq[n];
    vector<sprinkler> vec; 
    for(int i = 0; i < n; i++) freq[i] = 0;
    for(int i = 0 ; i < n; i++) {
        int x = gallery[i];
        if(x == -1) continue;
        int l = max(0, i - x);
        int r = min(n-1, i + x);
        sprinkler s;
        s.l = l;
        s.r = r;
        vec.push_back(s);
        for(int j = l; j <= r; j++) {
            freq[j]++;
        }
    }

    for(int i = 0; i < n; i++) {
        if(freq[i] == 0) return -1;
    }

    stable_sort(vec.begin(), vec.end(), [](sprinkler s1, sprinkler s2) { return s1.r-s1.l < s2.r-s2.l; });

    int sprinklers = vec.size();
    for(int i = 0; i < vec.size(); i++) {
        int l = vec[i].l;
        int r = vec[i].r;
        bool flag = false;
        for(int j = l; j <= r; j++) {
            if(freq[j] == 1) {
                flag = true;
                break;
            }
        }

        if(!flag) {
            for(int j = l; j <= r; j++) freq[j]--;
            sprinklers--;
        }
    }

    return sprinklers;
}

问题排查 #

1. 时间复杂度过高 #

原代码的核心问题是时间复杂度达到了O(n²)级别：每次处理洒水器时都需要遍历其覆盖的整个区间更新频率数组，当洒水器射程大、n超过1e4时，会直接超时无法通过大数据测试用例。

2. 非标准语法 #

代码中使用了可变长数组int freq[n]，这是GCC的扩展特性，不属于C++标准规范，在部分编译器下会直接编译失败，建议替换为vector<int> freq(n, 0)。

3. 思路的局限性 #

虽然小用例下逻辑可得到正确结果，但本质是通过删除无唯一覆盖点的洒水器得到无冗余集合，而贪心区间覆盖算法是更高效且通用的标准解法，时间复杂度仅为O(n log n)。

正确解法思路 #

标准的区间覆盖贪心算法步骤如下：

• 过滤未安装洒水器的位置，将所有可用洒水器转换为[左边界l, 右边界r]的区间形式。
• 将所有区间按左边界从小到大排序，左边界相同则按右边界从大到小排序。
• 初始化当前已覆盖的最远位置cur_end = 0，下一轮能覆盖的最远位置next_end = 0，计数res = 0，遍历索引i = 0。
• 当cur_end < n - 1时：
  • 遍历所有左边界小于等于cur_end的区间，记录最大的右边界作为next_end。
  • 如果next_end == cur_end，说明存在无法覆盖的缺口，返回-1。
  • 计数加1，更新cur_end = next_end。
• 最终返回计数即可。

内容的提问来源于stack exchange，提问作者ARJAV GARG