Cuente el número mínimo de fuentes que se activarán para cubrir todo el jardín

Hay un jardín unidimensional de longitud N. En cada posición del jardín de longitud N se ha instalado una fuente. Dada una array a[] tal que a[i] describe el límite de cobertura de i -ésima fuente. Una fuente puede cubrir el rango desde la posición max(i – a[i], 1) hasta min(i + a[i], N) . En principio, todas las fuentes están apagadas. La tarea es encontrar el número mínimo de fuentes necesarias para que se activen de modo que todo el jardín de longitud N pueda cubrirse con agua.

Ejemplos:

Entrada: a[] = {1, 2, 1}
Salida: 1
Explicación:
Para la posición 1: a[1] = 1, rango = 1 a 2
Para la posición 2: a[2] = 2, rango = 1 a 3
Para la posición 3: a[3] = 1, rango = 2 a 3
Por lo tanto, la fuente en la posición a[2] cubre todo el jardín.
Por lo tanto, la salida requerida es 1.

Entrada: a[] = {2, 1, 1, 2, 1} 
Salida:

 

Planteamiento: El problema se puede resolver usando Programación Dinámica . Siga los pasos a continuación para resolver el problema: 

  • recorrer la array y para cada índice de array, es decir, i -ésima fuente, encontrar la fuente más a la izquierda hasta la cual cubre la fuente actual.
  • Luego, busque la fuente más a la derecha que la fuente más a la izquierda obtuvo en el paso anterior y actualícela en la array dp[] .
  • Inicialice una variable cntFount para almacenar la cantidad mínima de fuentes que deben activarse.
  • Ahora, recorra la array dp[] y siga activando las fuentes desde la izquierda que cubre el máximo de fuentes actualmente a la derecha e incremente cntFount en 1 . Finalmente, imprima cntFount como la respuesta requerida.

A continuación se muestra la implementación del enfoque anterior.

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 approach
 
# 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>
Producción

1

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por dekay y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *