Dada una array arr[] de longitud N , la tarea es encontrar la cantidad mínima de premios requerida de modo que si dos elementos son adyacentes, los elementos con menor valor obtienen una menor cantidad de premios en comparación con sus elementos adyacentes con mayor valor.
Nota: Cada elemento obtendrá al menos un premio.
Ejemplos:
Entrada: arr[] = {1, 2, 2, 3}
Salida: 6
Explicación:
El elemento en el índice {0} obtendrá {1} premio.
El elemento en el índice {1} obtendrá {2} premios.
El elemento en el índice {2} obtendrá {1} premios.
El elemento en el índice {3} obtendrá {2} premios.
Entonces, el número total de premios necesarios para satisfacer
las condiciones anteriores es 6Entrada: arr[] = {3, 2, 2, 1}
Salida: 6
Explicación:
El elemento en el índice {0} obtendrá {2} premio.
El elemento en el índice {1} obtendrá {1} premios.
El elemento en el índice {2} obtendrá {2} premios.
El elemento en el índice {3} obtendrá {1} premios.
Entonces, el número total de premios necesarios para satisfacer
las condiciones anteriores es 6
Enfoque ingenuo: recorra los elementos de la array y, para cada elemento de la array, busque los elementos más pequeños consecutivos a la izquierda del elemento y encuentre los elementos más pequeños consecutivos a la derecha de ese índice.
Premio en el índice i = max (elementos consecutivos más pequeños a la izquierda, elementos consecutivos más pequeños a la derecha, 1)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// minimum prizes required such
// that adjacent smaller elements
// gets less number of prizes
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum
// number of required such that
// adjacent smaller elements gets
// less number of prizes
int findMinPrizes(int arr[], int n)
{
int totalPrizes = 0, j, x, y;
// Loop to iterate over every
// elements of the array
for (int i = 0; i < n; i++) {
x = 1;
j = i;
// Loop to find the consecutive
// smaller elements at left
while (j > 0 && arr[j] > arr[j - 1]) {
x++;
j--;
}
j = i;
y = 1;
// Loop to find the consecutive
// smaller elements at right
while (j < n - 1 && arr[j] > arr[j + 1]) {
y++;
j++;
}
totalPrizes += max({ x, y });
}
cout << totalPrizes << endl;
return 0;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
findMinPrizes(arr, n);
}
Java
// Java implementation to find the
// minimum prizes required such
// that adjacent smaller elements
// gets less number of prizes
import java.util.*;
class GFG{
// Function to find the minimum
// number of required such that
// adjacent smaller elements gets
// less number of prizes
static int findMinPrizes(int arr[], int n)
{
int totalPrizes = 0, j, x, y;
// Loop to iterate over every
// elements of the array
for (int i = 0; i < n; i++)
{
x = 1;
j = i;
// Loop to find the consecutive
// smaller elements at left
while (j > 0 && arr[j] > arr[j - 1])
{
x++;
j--;
}
j = i;
y = 1;
// Loop to find the consecutive
// smaller elements at right
while (j < n - 1 && arr[j] > arr[j + 1])
{
y++;
j++;
}
totalPrizes += Math.max(x, y );
}
System.out.print(totalPrizes + "\n");
return 0;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 2, 3 };
int n = arr.length;
findMinPrizes(arr, n);
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 implementation to find the # minimum prizes required such # that adjacent smaller elements # gets less number of prizes # Function to find the minimum # number of required such that # adjacent smaller elements gets # less number of prizes def findMinPrizes(arr, n): totalPrizes = 0 # Loop to iterate over every # elements of the array for i in range(n): x = 1 j = i # Loop to find the consecutive # smaller elements at left while (j > 0 and arr[j] > arr[j - 1]): x += 1 j -= 1 j = i y = 1 # Loop to find the consecutive # smaller elements at right while (j < n - 1 and arr[j] > arr[j + 1]): y += 1 j += 1 totalPrizes += max(x, y) print(totalPrizes) # Driver code arr = [ 1, 2, 2, 3 ] n = len(arr) findMinPrizes(arr, n) # This code is contributed by stutipathak31jan
C#
// C# implementation to find the
// minimum prizes required such
// that adjacent smaller elements
// gets less number of prizes
using System;
class GFG{
// Function to find the minimum
// number of required such that
// adjacent smaller elements gets
// less number of prizes
static int findMinPrizes(int []arr, int n)
{
int totalPrizes = 0, j, x, y;
// Loop to iterate over every
// elements of the array
for(int i = 0; i < n; i++)
{
x = 1;
j = i;
// Loop to find the consecutive
// smaller elements at left
while (j > 0 && arr[j] > arr[j - 1])
{
x++;
j--;
}
j = i;
y = 1;
// Loop to find the consecutive
// smaller elements at right
while (j < n - 1 &&
arr[j] > arr[j + 1])
{
y++;
j++;
}
totalPrizes += Math.Max(x, y);
}
Console.Write(totalPrizes + "\n");
return 0;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 2, 2, 3 };
int n = arr.Length;
findMinPrizes(arr, n);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript implementation to find the
// minimum prizes required such
// that adjacent smaller elements
// gets less number of prizes
// Function to find the minimum
// number of required such that
// adjacent smaller elements gets
// less number of prizes
function findMinPrizes(arr, n)
{
let totalPrizes = 0, j, x, y;
// Loop to iterate over every
// elements of the array
for (let i = 0; i < n; i++) {
x = 1;
j = i;
// Loop to find the consecutive
// smaller elements at left
while (j > 0 && arr[j] > arr[j - 1]) {
x++;
j--;
}
j = i;
y = 1;
// Loop to find the consecutive
// smaller elements at right
while (j < n - 1 && arr[j] > arr[j + 1]) {
y++;
j++;
}
totalPrizes += Math.max( x, y );
}
document.write(totalPrizes);
return 0;
}
let arr = [ 1, 2, 2, 3 ];
let n = arr.length;
findMinPrizes(arr, n);
// This code is contributed by divyesh072019.
</script>
Producción:
6
Análisis de rendimiento:
- Complejidad del tiempo: O(N 2 )
- Espacio Auxiliar: O(1)
Enfoque eficiente: la idea es precalcular el conteo de elementos más pequeños consecutivos a la izquierda y a la derecha para cada elemento de la array . Significa que, si un elemento a la izquierda es más pequeño, todos los elementos más pequeños a la izquierda de ese elemento también serán más pequeños que el elemento actual. es decir
if (arr[i-1] < arr[i])
smallerLeft[i] = smallerLeft[i-1] + 1
De manera similar, los elementos menores consecutivos se pueden calcular utilizando el hecho de que, si un elemento de la derecha es mayor que el elemento actual, los elementos mayores consecutivos de la derecha también serán mayores que el elemento actual. es decir
if (arr[i] < arr[i+1])
smallerRight[i] = smallerRight[i+1] + 1
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// minimum prizes required such
// that adjacent smaller elements
// gets less number of prizes
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum
// number of required such that
// adjacent smaller elements gets
// less number of prizes
int minPrizes(int arr[], int n)
{
int dpLeft[n];
dpLeft[0] = 1;
// Loop to compute the smaller
// elements at the left
for (int i = 1; i < n; i++) {
if (arr[i] > arr[i - 1]) {
dpLeft[i] = dpLeft[i - 1] + 1;
}
else {
dpLeft[i] = 1;
}
}
int dpRight[n];
dpRight[n - 1] = 1;
// Loop to find the smaller
// elements at the right
for (int i = n - 2; i >= 0; i--) {
if (arr[i] > arr[i + 1]) {
dpRight[i] = dpRight[i + 1] + 1;
}
else {
dpRight[i] = 1;
}
}
int totalPrizes = 0;
// Loop to find the minimum
// prizes required
for (int i = 0; i < n; i++) {
totalPrizes += max(dpLeft[i],
dpRight[i]);
}
cout << totalPrizes << endl;
return 0;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
minPrizes(arr, n);
return 0;
}
Java
// Java implementation to find the
// minimum prizes required such
// that adjacent smaller elements
// gets less number of prizes
import java.util.*;
class GFG{
// Function to find the minimum
// number of required such that
// adjacent smaller elements gets
// less number of prizes
static int minPrizes(int arr[], int n)
{
int []dpLeft = new int[n];
dpLeft[0] = 1;
// Loop to compute the smaller
// elements at the left
for(int i = 1; i < n; i++)
{
if (arr[i] > arr[i - 1])
{
dpLeft[i] = dpLeft[i - 1] + 1;
}
else
{
dpLeft[i] = 1;
}
}
int []dpRight = new int[n];
dpRight[n - 1] = 1;
// Loop to find the smaller
// elements at the right
for(int i = n - 2; i >= 0; i--)
{
if (arr[i] > arr[i + 1])
{
dpRight[i] = dpRight[i + 1] + 1;
}
else
{
dpRight[i] = 1;
}
}
int totalPrizes = 0;
// Loop to find the minimum
// prizes required
for(int i = 0; i < n; i++)
{
totalPrizes += Math.max(dpLeft[i],
dpRight[i]);
}
System.out.print(totalPrizes + "\n");
return 0;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 2, 3 };
int n = arr.length;
minPrizes(arr, n);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 implementation to find the # minimum prizes required such # that adjacent smaller elements # gets less number of prizes # Function to find the minimum # number of required such that # adjacent smaller elements gets # less number of prizes def minPrizes(arr, n): dpLeft = [0] * n dpLeft[0] = 1 # Loop to compute the smaller # elements at the left for i in range(n): if arr[i] > arr[i - 1]: dpLeft[i] = dpLeft[i - 1] + 1 else: dpLeft[i] = 1 dpRight = [0] * n dpRight[-1] = 1 # Loop to find the smaller # elements at the right for i in range(n - 2, -1, -1): if arr[i] > arr[i + 1]: dpRight[i] = dpRight[i + 1] + 1 else: dpRight[i] = 1 totalPrizes = 0 # Loop to find the minimum # prizes required for i in range(n): totalPrizes += max(dpLeft[i], dpRight[i]) print(totalPrizes) # Driver code arr = [ 1, 2, 2, 3 ] n = len(arr) minPrizes(arr, n) # This code is contributed by stutipathak31jan
C#
// C# implementation to find the
// minimum prizes required such
// that adjacent smaller elements
// gets less number of prizes
using System;
class GFG{
// Function to find the minimum
// number of required such that
// adjacent smaller elements gets
// less number of prizes
static int minPrizes(int []arr, int n)
{
int []dpLeft = new int[n];
dpLeft[0] = 1;
// Loop to compute the smaller
// elements at the left
for(int i = 1; i < n; i++)
{
if (arr[i] > arr[i - 1])
{
dpLeft[i] = dpLeft[i - 1] + 1;
}
else
{
dpLeft[i] = 1;
}
}
int []dpRight = new int[n];
dpRight[n - 1] = 1;
// Loop to find the smaller
// elements at the right
for(int i = n - 2; i >= 0; i--)
{
if (arr[i] > arr[i + 1])
{
dpRight[i] = dpRight[i + 1] + 1;
}
else
{
dpRight[i] = 1;
}
}
int totalPrizes = 0;
// Loop to find the minimum
// prizes required
for(int i = 0; i < n; i++)
{
totalPrizes += Math.Max(dpLeft[i],
dpRight[i]);
}
Console.Write(totalPrizes + "\n");
return 0;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 2, 2, 3 };
int n = arr.Length;
minPrizes(arr, n);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation to find the
// minimum prizes required such
// that adjacent smaller elements
// gets less number of prizes
// Function to find the minimum
// number of required such that
// adjacent smaller elements gets
// less number of prizes
function minPrizes(arr, n)
{
let dpLeft = new Array(n);
dpLeft[0] = 1;
// Loop to compute the smaller
// elements at the left
for(let i = 1; i < n; i++)
{
if (arr[i] > arr[i - 1])
{
dpLeft[i] = dpLeft[i - 1] + 1;
}
else
{
dpLeft[i] = 1;
}
}
let dpRight = new Array(n);
dpRight[n - 1] = 1;
// Loop to find the smaller
// elements at the right
for(let i = n - 2; i >= 0; i--)
{
if (arr[i] > arr[i + 1])
{
dpRight[i] = dpRight[i + 1] + 1;
}
else
{
dpRight[i] = 1;
}
}
let totalPrizes = 0;
// Loop to find the minimum
// prizes required
for(let i = 0; i < n; i++)
{
totalPrizes += Math.max(dpLeft[i],
dpRight[i]);
}
document.write(totalPrizes + "</br>");
return 0;
}
// Driver code
let arr = [ 1, 2, 2, 3 ];
let n = arr.length;
minPrizes(arr, n);
// This code is contributed by suresh07
</script>
Producción:
6
Análisis de rendimiento:
- Complejidad de tiempo: O(N)
- Espacio Auxiliar: O(N)