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: 2
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)