c++ - 给植物浇水（竞争性编程）

Question

我试图解决这个问题：

一个有植物的画廊被分成 n 个部分，编号为：0,1,2,3...n-1。每个分区都有安装洒水器的规定。分区 i 处范围为 x 的洒水器可以浇灌从 ix 到 i+x 的所有分区。给定一个由n个整数组成的数组gallery[ ]，其中gallery[i]是分区i处洒水器的范围（power==-1表示没有连接洒水器），返回需要开启洒水的最小洒水器数量完整的画廊。如果无法使用给定的洒水器浇灌全长，请打印 -1。

这就是我最终尝试的方式-

1. 创建一个频率数组，使第 i 个元素包含为画廊第 i 个部分浇水的洒水器的数量。
2. 如果在经过所有洒水器后此数组的任何元素为零，则返回 -1，即使所有洒水器都尝试过它们无法浇灌每个部分。
3. 然后，std::stable_sort所有洒水器根据其范围，按递增顺序排列。
4. 然后，如果有多余的洒水器，则从最小范围到最大范围移除。

我的实现相同-

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;
}

但我似乎仍然缺少一些东西，仍然不知道是什么。链接尝试我的代码： https ://practice.geeksforgeeks.org/problems/410d51d667ab93f2219b15126f001f32e8bb029e/0/?category[]=Greedy&category[]=Greedy&difficulty[]=1&page=1&query=category[]Greedydifficulty[]1page1category[]Greedy

标签： c++algorithmgreedy