Dada una array arr[] de N enteros y dos enteros S y M , la tarea es maximizar el elemento mínimo de la array incrementando cualquier subarreglo de tamaño S en 1 , M número de veces.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5, 6}, S = 2, M = 3
Salida: 3
Explicación:
A continuación se muestran las operaciones realizadas:
Operación 1: Seleccione el subarreglo {1, 2} y posteriores incremento, array arr[] se convierte en = {2, 3, 3, 4, 5, 6}.
Operación 2: Seleccione el subarreglo {2, 3} y después del incremento, el arreglo arr[] se convierte en = {3, 4, 3, 4, 5, 6}.
Operación 3: Seleccione el subarreglo {3, 4} y después del incremento, el arreglo arr[] se convierte en = {4, 5, 3, 4, 5, 6}.
Después de las operaciones anteriores, el elemento mínimo de la array es 3.Entrada: arr[] = {3, 5, 2, 7, 3}, S = 3, M = 3
Salida: 4
Explicación:
A continuación se muestran las operaciones realizadas:
Operación 1: Seleccione el subarreglo {3, 5, 2} y posteriores incremento, array arr[] se convierte en = {4, 6, 3, 7, 3}.
Operación 2: Seleccione el subarreglo {4, 6, 3} y después del incremento, el arreglo arr[] se convierte en = {5, 7, 4, 7, 3}.
Operación 3: seleccione el subarreglo {4, 7, 3} y después del incremento, el arreglo arr[] se convierte en = {5, 7, 5, 8, 4}.
Después de las operaciones anteriores, el elemento mínimo de la array es 4.
Enfoque: La idea es encontrar el elemento mínimo de la array M número de veces e incrementar los subarreglos de tamaño S desde ese elemento mínimo en 1 . Siga los pasos a continuación para resolver el problema:
- Recorra la array M número de veces y para cada iteración haga lo siguiente:
- Encuentre el elemento mínimo de la array arr[] . Sea el primer índice del elemento mínimo idx .
- Incremente el elemento mínimo actual en 1 .
- Ahora tome dos punteros leftIdx como idx – 1 y rightIdx como idx + 1 .
- Si el elemento en leftIdx es menor que el elemento en rightIdx entonces incremente A[leftIndex] en 1 y disminuya leftIndex en 1 . De lo contrario, incremente A[rightIndex] en 1 y rightIndex en 1 . Continúe con este paso hasta que se procesen los elementos (S – 1) .
- Después de las iteraciones anteriores, imprima el elemento mínimo de la array actualizada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return index of minimum
// element in the array
int min(int a[], int n)
{
// Initialize a[0] as minValue
int minIndex = 0, minValue = a[0], i;
// Traverse the array
for (i = 1; i < n; i++) {
// If a[i] < existing minValue
if (a[i] < minValue) {
minValue = a[i];
minIndex = i;
}
}
// Return the minimum index
return minIndex;
}
// Function that maximize the minimum
// element of array after incrementing
// subarray of size S by 1, M times
int maximizeMin(int A[], int N,
int S, int M)
{
int minIndex, left, right, i, j;
// Iterating through the array
// for M times
for (i = 0; i < M; i++) {
// Find minimum element index
minIndex = min(A, N);
// Increment the minimum value
A[minIndex]++;
// Storing the left index
// and right index
left = minIndex - 1;
right = minIndex + 1;
// Incrementing S - 1 minimum
// elements to the left and
// right of minValue
for (j = 0; j < S - 1; j++) {
// Reached extreme left
if (left == -1)
A[right++]++;
// Reached extreme right
else if (right == N)
A[left--]++;
else {
// Left value is minimum
if (A[left] < A[right])
A[left--]++;
// Right value is minimum
else
A[right++]++;
}
}
}
// Find the minValue in A[] after
// M operations
minIndex = min(A, N);
// Return the minimum value
return A[minIndex];
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
int S = 2, M = 3;
// Function Call
cout << maximizeMin(arr, N, S, M);
return 0;
}
Java
// Java program for the
// above approach
import java.util.*;
class solution{
// Function to return index
// of minimum element in the
// array
static int min1(int a[], int n)
{
// Initialize a[0] as
// minValue
int minIndex = 0,
minValue = a[0], i;
// Traverse the array
for (i = 1; i < n; i++)
{
// If a[i] < existing
// minValue
if (a[i] < minValue)
{
minValue = a[i];
minIndex = i;
}
}
// Return the minimum index
return minIndex;
}
// Function that maximize the minimum
// element of array after incrementing
// subarray of size S by 1, M times
static int maximizeMin(int A[], int N,
int S, int M)
{
int minIndex, left, right, i, j;
// Iterating through the
// array or M times
for (i = 0; i < M; i++)
{
// Find minimum element
// index
minIndex = min1(A, N);
// Increment the minimum
// value
A[minIndex]++;
// Storing the left index
// and right index
left = minIndex - 1;
right = minIndex + 1;
// Incrementing S - 1 minimum
// elements to the left and
// right of minValue
for (j = 0; j < S - 1; j++)
{
// Reached extreme left
if (left == -1)
A[right++]++;
// Reached extreme right
else if (right == N)
A[left--]++;
else
{
// Left value is minimum
if (A[left] < A[right])
A[left--]++;
// Right value is minimum
else
A[right++]++;
}
}
}
// Find the minValue in A[] after
// M operations
minIndex = min1(A, N);
// Return the minimum value
return A[minIndex];
}
// Driver Code
public static void main(String args[])
{
int []arr = {1, 2, 3,
4, 5, 6};
int N = arr.length;
int S = 2, M = 3;
// Function Call
System.out.print(maximizeMin(arr, N, S, M));
}
}
// This code is contributed by SURENDRA_GANGWAR
Python3
# Python3 program for the above approach # Function to return index of minimum # element in the array def min(a, n): # Initialize a[0] as minValue minIndex = 0 minValue = a[0] # Traverse the array for i in range(1, n): # If a[i] < existing minValue if (a[i] < minValue): minValue = a[i] minIndex = i # Return the minimum index return minIndex # Function that maximize the minimum # element of array after incrementing # subarray of size S by 1, M times def maximizeMin(A, N, S, M): minIndex, left, right = 0, 0, 0 # Iterating through the array # for M times for i in range(M): # Find minimum element index minIndex = min(A, N) # Increment the minimum value A[minIndex] += 1 # Storing the left index # and right index left = minIndex - 1 right = minIndex + 1 # Incrementing S - 1 minimum # elements to the left and # right of minValue for j in range(S - 1): # Reached extreme left if (left == -1): A[right] += 1 right += 1 # Reached extreme right elif (right == N): A[left] += 1 left -= 1 else: # Left value is minimum if (A[left] < A[right]): A[left] += 1 left -= 1 # Right value is minimum else: A[right] += 1 right += 1 # Find the minValue in A[] after # M operations minIndex = min(A, N) # Return the minimum value return A[minIndex] # Driver Code if __name__ == '__main__': arr = [ 1, 2, 3, 4, 5, 6 ] N = len(arr) S = 2 M = 3 #Function Call print(maximizeMin(arr, N, S, M)) # This code is contributed by mohit kumar 29
C#
// C# program for the
// above approach
using System;
class GFG{
// Function to return index
// of minimum element in the
// array
static int min1(int[] a,
int n)
{
// Initialize a[0] as
// minValue
int minIndex = 0,
minValue = a[0], i;
// Traverse the array
for (i = 1; i < n; i++)
{
// If a[i] < existing
// minValue
if (a[i] < minValue)
{
minValue = a[i];
minIndex = i;
}
}
// Return the minimum
// index
return minIndex;
}
// Function that maximize the
// minimum element of array
// after incrementing subarray
// of size S by 1, M times
static int maximizeMin(int[] A, int N,
int S, int M)
{
int minIndex, left, right, i, j;
// Iterating through the
// array or M times
for (i = 0; i < M; i++)
{
// Find minimum element
// index
minIndex = min1(A, N);
// Increment the minimum
// value
A[minIndex]++;
// Storing the left index
// and right index
left = minIndex - 1;
right = minIndex + 1;
// Incrementing S - 1 minimum
// elements to the left and
// right of minValue
for (j = 0; j < S - 1; j++)
{
// Reached extreme left
if (left == -1)
A[right++]++;
// Reached extreme right
else if (right == N)
A[left--]++;
else
{
// Left value is minimum
if (A[left] < A[right])
A[left--]++;
// Right value is minimum
else
A[right++]++;
}
}
}
// Find the minValue in A[] after
// M operations
minIndex = min1(A, N);
// Return the minimum value
return A[minIndex];
}
// Driver code
static void Main()
{
int[] arr = {1, 2, 3,
4, 5, 6};
int N = arr.Length;
int S = 2, M = 3;
// Function Call
Console.Write(maximizeMin(arr, N,
S, M));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to return index
// of minimum element in the
// array
function min1(a, n)
{
// Initialize a[0] as
// minValue
let minIndex = 0,
minValue = a[0], i;
// Traverse the array
for (i = 1; i < n; i++)
{
// If a[i] < existing
// minValue
if (a[i] < minValue)
{
minValue = a[i];
minIndex = i;
}
}
// Return the minimum index
return minIndex;
}
// Function that maximize the minimum
// element of array after incrementing
// subarray of size S by 1, M times
function maximizeMin(A, N, S, M)
{
let minIndex, left, right, i, j;
// Iterating through the
// array or M times
for (i = 0; i < M; i++)
{
// Find minimum element
// index
minIndex = min1(A, N);
// Increment the minimum
// value
A[minIndex]++;
// Storing the left index
// and right index
left = minIndex - 1;
right = minIndex + 1;
// Incrementing S - 1 minimum
// elements to the left and
// right of minValue
for (j = 0; j < S - 1; j++)
{
// Reached extreme left
if (left == -1)
A[right++]++;
// Reached extreme right
else if (right == N)
A[left--]++;
else
{
// Left value is minimum
if (A[left] < A[right])
A[left--]++;
// Right value is minimum
else
A[right++]++;
}
}
}
// Find the minValue in A[] after
// M operations
minIndex = min1(A, N);
// Return the minimum value
return A[minIndex];
}
// Driver Code
let arr = [1, 2, 3,
4, 5, 6];
let N = arr.length;
let S = 2, M = 3;
// Function Call
document.write(maximizeMin(arr, N, S, M));
</script>
Producción:
3
Complejidad temporal: O(M*N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA