Dada una array A[] que consta de N enteros, donde cada valor representa las calificaciones del i -ésimo estudiante, la tarea es encontrar la cantidad mínima de chocolates que se requieren para distribuir de manera que:
- Cada estudiante debe ser premiado con al menos un chocolate.
- Un estudiante con calificaciones más altas debe recibir más chocolates que sus estudiantes adyacentes.
Ejemplos:
Entrada: A[] = {10, 30, 20}
Salida: 4
Explicación: Dado que 30 es más grande que su adyacente, el segundo estudiante debe obtener más chocolates. Por lo tanto, los chocolates mínimos se pueden distribuir como {1, 2, 1} = 1 + 2 + 1 = 4Entrada: A[] = {23, 14, 15, 14, 56, 29, 14}
Salida: 12
Método 1:
Enfoque: el problema se puede resolver utilizando el enfoque codicioso . Siga los pasos a continuación para resolver el problema:
- Inicialice la array B[] de longitud N con 1 .
- Recorra de izquierda a derecha de i = 1 a N – 1 , actualizando B[i] como B[i] = B[i-1]+1 si A[i] es mayor que A[i-1] .
- Después de completar el paso anterior, recorra nuevamente de derecha a izquierda desde i = N – 2 a 0 , actualizando B[i] como B[i] = max(B[i], B[i+1]+1) si A [i] es mayor que A[i + 1] . De lo contrario, actualice B[i] como B[i] = max(B[i], 1) .
- Después de atravesar, calcule la suma de la array B[] e imprímala como el número mínimo de caramelos necesarios.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// FUnction to print minimum number
// of candies required
void minChocolates(int A[], int N)
{
int B[N];
// Distribute 1 chocolate to each
for (int i = 0; i < N; i++) {
B[i] = 1;
}
// Traverse from left to right
for (int i = 1; i < N; i++) {
if (A[i] > A[i - 1])
B[i] = B[i - 1] + 1;
else
B[i] = 1;
}
// Traverse from right to left
for (int i = N - 2; i >= 0; i--) {
if (A[i] > A[i + 1])
B[i] = max(B[i + 1] + 1, B[i]);
else
B[i] = max(B[i], 1);
}
// Initialize sum
int sum = 0;
// Find total sum
for (int i = 0; i < N; i++) {
sum += B[i];
}
// Return sum
cout << sum << "\n";
}
// Driver Code
int main()
{
// Given array
int A[] = { 23, 14, 15, 14, 56, 29, 14 };
// Size of the given array
int N = sizeof(A) / sizeof(A[0]);
minChocolates(A, N);
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// FUnction to print minimum number
// of candies required
static void minChocolates(int A[], int N)
{
int[] B = new int[N];
// Distribute 1 chocolate to each
for (int i = 0; i < N; i++) {
B[i] = 1;
}
// Traverse from left to right
for (int i = 1; i < N; i++) {
if (A[i] > A[i - 1])
B[i] = B[i - 1] + 1;
else
B[i] = 1;
}
// Traverse from right to left
for (int i = N - 2; i >= 0; i--) {
if (A[i] > A[i + 1])
B[i] = Math.max(B[i + 1] + 1, B[i]);
else
B[i] = Math.max(B[i], 1);
}
// Initialize sum
int sum = 0;
// Find total sum
for (int i = 0; i < N; i++) {
sum += B[i];
}
// Return sum
System.out.print(sum + "\n");
}
// Driver Code
public static void main(String[] args)
{
// Given array
int A[] = { 23, 14, 15, 14, 56, 29, 14 };
// Size of the given array
int N = A.length;
minChocolates(A, N);
}
}
// This code contributed by shikhasingrajput
Python3
# Python3 program for the above approach # Function to print minimum number # of candies required def minChocolates(A, N): B = [1 for i in range(N)] # Traverse from left to right for i in range(1, N): if (A[i] > A[i - 1]): B[i] = B[i - 1] + 1 else: B[i] = 1 # Traverse from right to left for i in range(N - 2, -1, -1): if (A[i] > A[i + 1]): B[i] = max(B[i + 1] + 1, B[i]) else: B[i] = max(B[i], 1) # Initialize sum sum = 0 # Find total sum for i in range(N): sum += B[i] # Return sum print(sum) # Driver Code if __name__ == '__main__': # Given array A = [23, 14, 15, 14, 56, 29, 14] # Size of the given array N = len(A) minChocolates(A, N) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
public class GFG {
// FUnction to print minimum number
// of candies required
static void minChocolates(int[] A, int N)
{
int[] B = new int[N];
// Distribute 1 chocolate to each
for (int i = 0; i < N; i++) {
B[i] = 1;
}
// Traverse from left to right
for (int i = 1; i < N; i++) {
if (A[i] > A[i - 1])
B[i] = B[i - 1] + 1;
else
B[i] = 1;
}
// Traverse from right to left
for (int i = N - 2; i >= 0; i--) {
if (A[i] > A[i + 1])
B[i] = Math.Max(B[i + 1] + 1, B[i]);
else
B[i] = Math.Max(B[i], 1);
}
// Initialize sum
int sum = 0;
// Find total sum
for (int i = 0; i < N; i++) {
sum += B[i];
}
// Return sum
Console.Write(sum + "\n");
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int[] A = { 23, 14, 15, 14, 56, 29, 14 };
// Size of the given array
int N = A.Length;
minChocolates(A, N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program for the above approach
// FUnction to print minimum number
// of candies required
function minChocolates(A, N)
{
let B = new Array(N).fill(0);
// Distribute 1 chocolate to each
for (let i = 0; i < N; i++) {
B[i] = 1;
}
// Traverse from left to right
for (let i = 1; i < N; i++) {
if (A[i] > A[i - 1])
B[i] = B[i - 1] + 1;
else
B[i] = 1;
}
// Traverse from right to left
for (let i = N - 2; i >= 0; i--) {
if (A[i] > A[i + 1])
B[i] = Math.max(B[i + 1] + 1, B[i]);
else
B[i] = Math.max(B[i], 1);
}
// Initialize sum
let sum = 0;
// Find total sum
for (let i = 0; i < N; i++) {
sum += B[i];
}
// Return sum
document.write(sum + "<br/>");
}
// Driver Code
// Given array
let A = [ 23, 14, 15, 14, 56, 29, 14 ];
// Size of the given array
let N = A.length;
minChocolates(A, N);
</script>
12
Complejidad de tiempo: O(N) donde N es la longitud de la array dada.
Espacio Auxiliar: O(N)
Método 2: enfoque eficiente
En una observación cuidadosa, la complejidad del espacio se puede reducir a O (1).
I. Observación:
- La array de marcas será una combinación de subarreglos estrictamente crecientes, estrictamente decrecientes o planos (el valor es el mismo que el de ambos vecinos).
- Para minimizar la cantidad total de chocolates distribuidos, la cantidad de chocolates que recibe una persona y al menos uno de los vecinos debe **diferir en 1 o menos.
** Una excepción de la segunda observación se menciona a continuación.
II. repartiendo bombones
Caso 1: el subarreglo es estrictamente creciente
Si los valores son estrictamente crecientes, el número de chocolates dados al i -ésimo estudiante será uno más que el número de chocolates dados al (i-1) -ésimo estudiante (para cualquier i > 0)
Se le dará un chocolate a la persona más a la izquierda en el subarreglo, dos al siguiente y así sucesivamente hasta la persona con las calificaciones más altas.
Para un subarreglo estrictamente creciente de longitud k, la distribución de chocolate será [1, 2, …, k].
Caso 2: el subarreglo es estrictamente decreciente
El número de chocolates entregados al i -ésimo estudiante será uno más que los chocolates entregados al (i+1) -ésimo estudiante (para cualquier i <n-1) con un chocolate a la persona más a la derecha y el número máximo a la persona más a la izquierda del subarreglo .
Para un subarreglo estrictamente decreciente de longitud k, la distribución chocolate será [k, k-1, … ,1].
Caso 3: secuencia plana
Teniendo en cuenta que a un alumno con las mejores notas se le premiará con más bombones que a sus vecinos. Entonces no hay dependencia si los valores son iguales. Se asignará un valor mínimo para un resultado óptimo.
Se le dará un chocolate a la persona en la posición i si ambos valores adyacentes son iguales a a[i], es decir, a[i-1] == a[i] == a[i+1]
Para un subarreglo plano de longitud k, la distribución de chocolate será [1, 1, … ,1].
**La diferencia para un valor asignado con ambos vecinos puede ser mayor que 1, si hay un solo elemento en secuencia plana y se encuentra exactamente entre una secuencia creciente y decreciente
Puntos de transición: Los puntos donde cambia la tendencia (naturaleza creciente/decreciente/plana) del subarreglo.
- Punto pico: punto que es el punto final de una secuencia creciente y el punto inicial de otra secuencia decreciente
entonces el valor asignado será max(k1, k2)
donde k1 – valor obtenido de la secuencia creciente,
k2 – valor obtenido de la secuencia decreciente.
Este punto se considerará como parte de una secuencia creciente o decreciente únicamente
tercero Resultado :
Como los valores en una secuencia creciente/decreciente difieren en 1, la cantidad de chocolates distribuidos a los estudiantes en un subarreglo específico de k elementos será la suma de k números naturales. Y el conteo será k para una secuencia plana ya que todos los valores son 1. El valor requerido será la suma total de los resultados de los subarreglos.
IV. Implementación:
Considere las variables i, j apuntando inicialmente al primer elemento, val = 1, res = 0.
Después de atravesar la array, res da el número total de chocolates distribuidos.
val mientras itera el índice j (en subarreglo creciente/plano) representa el número de chocolates recibidos por la persona en j
Si el subarreglo es creciente o una secuencia plana, se agrega val a res; i, j avanzan y val se actualiza de acuerdo con el siguiente valor (a[j + 1]).
Si el subarreglo está disminuyendo, i apunta al punto inicial del subarreglo y j avanza hasta el siguiente punto de transición. val, res no se actualizan hasta el final del subarreglo. En este caso, val contiene el valor del elemento pico obtenido del subarreglo anterior. Al final de la secuencia decreciente, res se actualiza usando la función get_sum y val se actualiza para señalar la cantidad de chocolates que tiene la siguiente persona.
V. Ejemplo:
Entrada: A[ ] = {1, 2, 10, 7, 6, 4, 5, 5, 5, 6}
Salida : 19
Explicación:
subarreglo — tipo de secuencia — conteo de chocolates
A[0-1] — secuencia creciente — [1, 2]
A[2-5] — secuencia decreciente — [4, 3, 2, 1]
A[5-6] — secuencia creciente — [1, 2]
A[7-7] — secuencia plana — [1]
A[8-9] — secuencia creciente — [1, 2]
A[2], A[9] son puntos pico
La distribución de chocolates será
[1, 2, 4, 3, 2, 1, 2, 1, 1, 2]
Suma de todos los valores = 19
A continuación se muestra el código para el enfoque anterior
C
// C program for above approach
#include <stdio.h>
// Helper function to get sum of decreasing sequence
int get_sum(int peak, int start, int end)
{
/* peak is the value obtained at peak point
from previous flat/increasing sequence */
/* value obtained from decreasing sequence
also the count of values in the sequence*/
int count = end - start + 1;
/* assigning max of values obtained from
increasing and decreasing sequences */
peak = (peak > count) ? peak : count;
/* sum of count - 1 values & peak value
sum of natural numbers : (n * (n + 1))/2 */
int s = peak + (((count - 1) * count) >> 1);
return s;
}
// Function to return minimum number of chocolates
int minChocolates(int a[], int n)
{
int i = 0, j = 0;
int res = 0, val = 1;
while (j < n - 1) {
if (a[j] > a[j + 1]) {
// decreasing sequence
j += 1;
continue;
}
if (i == j)
// add the chocolates received by that person
res += val;
else {
// end point of decreasing sequence
res += get_sum(val, i, j);
val = 1; // reset value at that index
}
if (a[j] < a[j + 1])
// increasing sequence
val += 1;
else
// flat sequence
val = 1;
j += 1;
i = j;
}
// add value of chocolates at position n-1
if (i == j)
res += val;
else
res += get_sum(val, i, j);
return res;
}
// Driver code
int main()
{
int a[] = { 5, 5, 4, 3, 2, 1 };
int n = sizeof(a) / sizeof(a[0]);
printf("Minimum number of chocolates = %d",
minChocolates(a, n));
return 0;
}
// This code is contributed by saitejagampala
C++
// C++ program for above approach
#include <iostream>
using namespace std;
// Helper function to get sum of decreasing sequence
int get_sum(int peak, int start, int end)
{
/* peak is the value obtained at peak point
from previous flat/increasing sequence */
/* value obtained from decreasing sequence
also the count of values in the sequence*/
int count = end - start + 1;
/* assigning max of values obtained from
increasing and decreasing sequences */
peak = max(peak, count);
/* sum of count - 1 values & peak value
sum of natural numbers : (n * (n + 1))/2 */
int s = peak + (((count - 1) * count) >> 1);
return s;
}
// Function to return minimum number of chocolates
int minChocolates(int a[], int n)
{
int i = 0, j = 0;
int res = 0, val = 1;
while (j < n - 1) {
if (a[j] > a[j + 1]) {
// decreasing sequence
j += 1;
continue;
}
if (i == j)
// add the chocolates received by that person
res += val;
else {
// end point of decreasing sequence
res += get_sum(val, i, j);
val = 1; // reset value at that index
}
if (a[j] < a[j + 1])
// increasing sequence
val += 1;
else
// flat sequence
val = 1;
j += 1;
i = j;
}
// add value of chocolates at position n-1
if (i == j)
res += val;
else
res += get_sum(val, i, j);
return res;
}
// Driver code
int main()
{
int a[] = { 5, 5, 4, 3, 2, 1 };
int n = sizeof(a) / sizeof(a[0]);
cout << "Minimum number of chocolates = "
<< minChocolates(a, n) << "\n";
return 0;
}
// This code is contributed by saitejagampala
Java
// Java program for above approach
import java.io.*;
class GFG {
public static void main(String[] args)
{
int[] a = { 5, 5, 4, 3, 2, 1 };
int n = a.length;
System.out.print("Minimum number of chocolates = "
+ minChocolates(a, n));
}
// Function to return minimum number of chocolates
public static int minChocolates(int[] a, int n)
{
int i = 0, j = 0;
int res = 0, val = 1;
while (j < n - 1) {
if (a[j] > a[j + 1]) {
// decreasing sequence
j += 1;
continue;
}
if (i == j)
// add the chocolates received by that
// person
res += val;
else {
// end point of decreasing sequence
res += get_sum(val, i, j);
val = 1; // reset value at that index
}
if (a[j] < a[j + 1])
// increasing sequence
val += 1;
else
// flat sequence
val = 1;
j += 1;
i = j;
}
// add value of chocolates at position n-1
if (i == j)
res += val;
else
res += get_sum(val, i, j);
return res;
}
// helper function to get sum of decreasing sequence
public static int get_sum(int peak, int start, int end)
{
/* peak is the value obtained at peak point
from previous flat/increasing sequence */
/* value obtained from decreasing sequence
also the count of values in the sequence*/
int count = end - start + 1;
/* assigning max of values obtained from
increasing and decreasing sequences */
peak = (peak > count) ? peak : count;
/* sum of count - 1 values & peak value
sum of natural numbers : (n * (n + 1))/2 */
int s = peak + (((count - 1) * count) >> 1);
return s;
}
}
// This code is contributed by saitejagampala
Python3
# Python3 program for above approach
# Function to return minimum number of chocolates
def minChocolates(a, n):
i, j = 0, 0
val, res = 1, 0
while(j < n - 1):
if(a[j] > a[j + 1]):
# decreasing sequence
j += 1
continue
if(i == j):
# add the chocolates received by that person
res += val
else:
# end point of decreasing sequence
res += get_sum(val, i, j)
val = 1 # reset value at that index
if(a[j] < a[j + 1]):
# increasing sequence
val += 1
else:
# flat sequence
val = 1
j += 1
i = j
# add value of chocolates at position n-1
if(i == j):
res += val
else:
res += get_sum(val, i, j)
return res
# Helper function to get sum of decreasing sequence
def get_sum(peak, start, end):
# peak is the value obtained at peak point
# from previous flat/increasing sequence
# value obtained from decreasing sequence
# also the count of values in the sequence
count = end - start + 1
# assigning max of values obtained from increasing
# and decreasing sequences
peak = max(peak, count)
# sum of count - 1 values & peak value
# sum of natural numbers : (n * (n + 1))/2
s = peak + (((count-1) * count) >> 1)
return s
# Driver code
if __name__ == '__main__':
a = [5, 5, 4, 3, 2, 1]
n = len(a)
print('Minimum number of chocolates =', minChocolates(a, n))
# This code is contributed by saitejagampala
Javascript
<script>
// Javascript program for above approach
// Function to return minimum number of chocolates
function minChocolates(a,n)
{
let i = 0, j = 0;
let res = 0, val = 1;
while (j < n - 1)
{
if (a[j] > a[j + 1])
{
// decreasing sequence
j += 1;
continue;
}
if (i == j)
// add the chocolates received by that
// person
res += val;
else
{
// end point of decreasing sequence
res += get_sum(val, i, j);
val = 1; // reset value at that index
}
if (a[j] < a[j + 1])
// increasing sequence
val += 1;
else
// flat sequence
val = 1;
j += 1;
i = j;
}
// add value of chocolates at position n-1
if (i == j)
res += val;
else
res += get_sum(val, i, j);
return res;
}
// helper function to get sum of decreasing sequence
function get_sum(peak,start,end)
{
/* peak is the value obtained at peak point
from previous flat/increasing sequence */
/* value obtained from decreasing sequence
also the count of values in the sequence*/
let count = end - start + 1;
/* assigning max of values obtained from
increasing and decreasing sequences */
peak = (peak > count) ? peak : count;
/* sum of count - 1 values & peak value
sum of natural numbers : (n * (n + 1))/2 */
let s = peak + (((count - 1) * count) >> 1);
return s;
}
let a = [5, 5, 4, 3, 2, 1];
let n = a.length;
document.write("Minimum number of chocolates = "
+ minChocolates(a, n));
// This code is contributed by unknown2108
</script>
C#
// C# program for above approach
using System;
public class GFG{
// Function to return minimum number of chocolates
public static int minChocolates(int[] a, int n)
{
int i = 0, j = 0;
int res = 0, val = 1;
while (j < n - 1) {
if (a[j] > a[j + 1]) {
// decreasing sequence
j += 1;
continue;
}
if (i == j)
// add the chocolates received by that
// person
res += val;
else {
// end point of decreasing sequence
res += get_sum(val, i, j);
val = 1; // reset value at that index
}
if (a[j] < a[j + 1])
// increasing sequence
val += 1;
else
// flat sequence
val = 1;
j += 1;
i = j;
}
// add value of chocolates at position n-1
if (i == j)
res += val;
else
res += get_sum(val, i, j);
return res;
}
// helper function to get sum of decreasing sequence
public static int get_sum(int peak, int start, int end)
{
/* peak is the value obtained at peak point
from previous flat/increasing sequence */
/* value obtained from decreasing sequence
also the count of values in the sequence*/
int count = end - start + 1;
/* assigning max of values obtained from
increasing and decreasing sequences */
peak = (peak > count) ? peak : count;
/* sum of count - 1 values & peak value
sum of natural numbers : (n * (n + 1))/2 */
int s = peak + (((count - 1) * count) >> 1);
return s;
}
static public void Main (){
int[] a = { 5, 5, 4, 3, 2, 1 };
int n = a.Length;
Console.WriteLine("Minimum number of chocolates = "
+ minChocolates(a, n));
}
}
// This code is contributed by patel2127
Minimum number of chocolates = 16
Complejidad de tiempo: O (N), N es la longitud de la array
Complejidad espacial : O(1)
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA