Подсчитайте минимальное количество фонтанов, которые нужно активировать, чтобы покрыть весь сад

Опубликовано: 8 Января, 2022

Имеется одномерный сад длиной N. В каждой позиции сада длиной N установлен фонтан. Дан массив a [] такой, что a [i] описывает предел покрытия i- го фонтана. Фонтан может охватывать диапазон от позиции max (i - a [i], 1) до min (i + a [i], N) . Сначала все фонтаны выключены. Задача состоит в том, чтобы найти минимальное количество фонтанов, которое необходимо активировать, чтобы весь сад длиной N мог быть покрыт водой.

Примеры:

Input: a[] = {1, 2, 1}
Output: 1
Explanation:
For position 1: a[1] = 1, range = 1 to 2
For position 2: a[2] = 2, range = 1 to 3
For position 3: a[3] = 1, range = 2 to 3
Therefore, the fountain at position a[2] covers the whole garden.
Therefore, the required output is 1.

Input: a[] = {2, 1, 1, 2, 1} 
Output: 2 

Подход: проблему можно решить с помощью динамического программирования. Выполните следующие действия, чтобы решить проблему:

  • пройти по массиву и для каждого индекса массива, т.е. i- го фонтана, найти крайний левый фонтан, до которого покрывает текущий фонтан.
  • Затем найдите крайний правый фонтан, который перекрывает крайний левый фонтан, полученный на предыдущем шаге, и обновите его в массиве dp [].
  • Инициализируйте переменную cntFount для хранения минимального количества фонтанов, которые необходимо активировать.
  • Теперь пройдитесь по массиву dp [] и продолжайте активировать фонтаны слева, которые покрывают максимальное количество фонтанов, находящихся в данный момент справа, и увеличивайте cntFount на 1 . Наконец, выведите cntFount как требуемый ответ.

Below is the implementation of the above approach.

C++14

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum
// number of fountains to be
// activated
int minCntFoun(int a[], int N)
{
 
    // dp[i]: Stores the position of
    // rightmost fountain that can
    // be covered by water of leftmost
    // fountain of the i-th fountain
    int dp[N];
     
    // initializing all dp[i] values to be -1,
    // so that we don"t get garbage value
      for(int i=0;i<N;i++){
          dp[i]=-1;
    }
 
    // Stores index of leftmost fountain
    // in the range of i-th fountain
    int idxLeft;
 
    // Stores index of rightmost fountain
    // in the range of i-th fountain
    int idxRight;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
        idxLeft = max(i - a[i], 0);
        idxRight = min(i + (a[i] + 1), N);
        dp[idxLeft] = max(dp[idxLeft],
                          idxRight);
    }
 
    // Stores count of fountains
    // needed to be activated
    int cntfount = 1;
 
    idxRight = dp[0];
 
    // Stores index of next fountain
    // that needed to be activated
    // initializing idxNext with -1
    // so that we don"t get garbage value
    int idxNext=-1;
 
    // Traverse dp[] array
    for (int i = 0; i < N; i++)
    {
        idxNext = max(idxNext,
                      dp[i]);
 
        // If left most fountain
        // cover all its range
        if (i == idxRight)
        {
            cntfount++;
            idxRight = idxNext;
        }
    }
 
    return cntfount;
}
 
// Driver Code
int main()
{
    int a[] = { 1, 2, 1 };
    int N = sizeof(a) / sizeof(a[0]);
    cout << minCntFoun(a, N);
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG {
 
    // Function to find minimum
    // number of fountains to be
    // activated
    static int minCntFoun(int a[], int N)
    {
 
        // dp[i]: Stores the position of
        // rightmost fountain that can
        // be covered by water of leftmost
        // fountain of the i-th fountain
        int[] dp = new int[N];
        for(int i=0;i<N;i++)
        {
             dp[i]=-1;
        }
 
        // Stores index of leftmost fountain
        // in the range of i-th fountain
        int idxLeft;
 
        // Stores index of rightmost fountain
        // in the range of i-th fountain
        int idxRight;
 
        // Traverse the array
        for (int i = 0; i < N; i++)
        {
            idxLeft = Math.max(i - a[i], 0);
            idxRight = Math.min(i + (a[i] + 1), N);
            dp[idxLeft] = Math.max(dp[idxLeft],
                                   idxRight);
        }
 
        // Stores count of fountains
        // needed to be activated
        int cntfount = 1;
 
        // Stores index of next fountain
        // that needed to be activated
        int idxNext = 0;
        idxRight = dp[0];
 
        // Traverse dp[] array
        for (int i = 0; i < N; i++)
        {
            idxNext = Math.max(idxNext, dp[i]);
 
            // If left most fountain
            // cover all its range
            if (i == idxRight)
            {
                cntfount++;
                idxRight = idxNext;
            }
        }
        return cntfount;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int a[] = { 1, 2, 1 };
        int N = a.length;
 
        System.out.print(minCntFoun(a, N));
    }
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program to implement
# the above appraoch
 
# Function to find minimum
# number of fountains to be
# activated
 
 
def minCntFoun(a, N):
 
    # dp[i]: Stores the position of
    # rightmost fountain that can
    # be covered by water of leftmost
    # fountain of the i-th fountain
    dp = [0] * N
    for i in range(N):
      dp[i] = -1
 
    # Traverse the array
    for i in range(N):
        idxLeft = max(i - a[i], 0)
        idxRight = min(i + (a[i] + 1), N)
        dp[idxLeft] = max(dp[idxLeft],
                          idxRight)
 
    # Stores count of fountains
    # needed to be activated
    cntfount = 1
 
    idxRight = dp[0]
 
    # Stores index of next fountain
    # that needed to be activated
    idxNext = 0
 
    # Traverse dp[] array
    for i in range(N):
        idxNext = max(idxNext,
                      dp[i])
 
        # If left most fountain
        # cover all its range
        if (i == idxRight):
            cntfount += 1
            idxRight = idxNext
 
    return cntfount
 
 
# Driver code
if __name__ == "__main__":
 
    a = [1, 2, 1]
    N = len(a)
 
    print(minCntFoun(a, N))
 
# This code is contributed by Shivam Singh

C#

// C# program to implement
// the above approach
using System;
class GFG {
 
    // Function to find minimum
    // number of fountains to be
    // activated
    static int minCntFoun(int[] a, int N)
    {
        // dp[i]: Stores the position of
        // rightmost fountain that can
        // be covered by water of leftmost
        // fountain of the i-th fountain
        int[] dp = new int[N];
        for (int i = 0; i < N; i++)
        {
            dp[i] = -1;
        }
 
        // Stores index of leftmost
        // fountain in the range of
        // i-th fountain
        int idxLeft;
 
        // Stores index of rightmost
        // fountain in the range of
        // i-th fountain
        int idxRight;
 
        // Traverse the array
        for (int i = 0; i < N; i++) {
            idxLeft = Math.Max(i - a[i], 0);
            idxRight = Math.Min(i + (a[i] + 1),
                                N);
            dp[idxLeft] = Math.Max(dp[idxLeft],
                                   idxRight);
        }
 
        // Stores count of fountains
        // needed to be activated
        int cntfount = 1;
 
        // Stores index of next
        // fountain that needed
        // to be activated
        int idxNext = 0;
        idxRight = dp[0];
 
        // Traverse []dp array
        for (int i = 0; i < N; i++)
        {
            idxNext = Math.Max(idxNext, dp[i]);
 
            // If left most fountain
            // cover all its range
            if (i == idxRight)
            {
                cntfount++;
                idxRight = idxNext;
            }
        }
        return cntfount;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int[] a = { 1, 2, 1 };
        int N = a.Length;
 
        Console.Write(minCntFoun(a, N));
    }
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
 
// Javascript program to implement
// the above approach
 
// Function to find minimum
// number of fountains to be
// activated
function minCntFoun(a, N)
{
     
    // dp[i]: Stores the position of
    // rightmost fountain that can
    // be covered by water of leftmost
    // fountain of the i-th fountain
    let dp = [];
    for(let i = 0; i < N; i++)
    {
         dp[i] = -1;
    }
 
    // Stores index of leftmost fountain
    // in the range of i-th fountain
    let idxLeft;
 
    // Stores index of rightmost fountain
    // in the range of i-th fountain
    let idxRight;
 
    // Traverse the array
    for(let i = 0; i < N; i++)
    {
        idxLeft = Math.max(i - a[i], 0);
        idxRight = Math.min(i + (a[i] + 1), N);
        dp[idxLeft] = Math.max(dp[idxLeft],
                               idxRight);
    }
 
    // Stores count of fountains
    // needed to be activated
    let cntfount = 1;
 
    // Stores index of next fountain
    // that needed to be activated
    let idxNext = 0;
    idxRight = dp[0];
 
    // Traverse dp[] array
    for(let i = 0; i < N; i++)
    {
        idxNext = Math.max(idxNext, dp[i]);
 
        // If left most fountain
        // cover all its range
        if (i == idxRight)
        {
            cntfount++;
            idxRight = idxNext;
        }
    }
    return cntfount;
}
 
// Driver Code
let a = [ 1, 2, 1 ];
let N = a.length;
 
document.write(minCntFoun(a, N));
 
// This code is contributed by souravghosh0416
 
</script>
Output
1

Сложность времени: O (N)
Вспомогательное пространство: O (N)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Mathematical Курсы по тестированию

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Что такое тестирование: подробное объяснение целей, видов, процессов и метрик качества в разработке программного обеспечения
2 Января, 2026
Кто такой тестировщик: чем занимается QA-специалист, какие навыки нужны и как войти в профессию тестирования ПО
2 Января, 2026
Лучшие бесплатные курсы по тестированию (QA): где учиться с нуля и как выбрать программу под свою цель
30 Декабря, 2025
Курс «Тестировщик: быстрый старт в IT» от Нетологии — подробный обзор бесплатного обучения QA с нуля
29 Декабря, 2025
Разделите два числа с помощью двоичного поиска без использования оператора / и %
15 Февраля, 2023
Подсчитайте пары, разница между которыми и индексами различна.
15 Февраля, 2023
Назначьте N задач N людям, чтобы минимизировать общее время
14 Февраля, 2023
Разделить массив на максимальное количество подмассивов, чтобы сумма чередующихся сумм была равна 0
14 Февраля, 2023