Dada una array arr[] que consta de N enteros positivos y un entero positivo K , la tarea es minimizar el elemento máximo presente en la array dividiendo como máximo K elementos de la array en dos números iguales a su valor.
Ejemplos:
Entrada: arr[] = {2, 4, 8, 2}, K = 4
Salida: 2
Explicación:
Se requiere realizar la siguiente secuencia de operaciones:
Operación 1: Dividir arr[1] (= 4) a {2, 2} modifica la array a {2, 2, 2, 8, 2}.
Operación 2: Dividir arr[3] (= 8) a {2, 6} modifica la array a {2, 2, 2, 2, 6, 2}.
Operación 3: Dividir arr[4] (= 6) a {2, 4} modifica la array a {2, 2, 2, 2, 2, 4, 2}.
Operación 4: Dividir arr[5] (= 4) a {2, 2} modifica la array a {2, 2, 2, 2, 2, 2, 2, 2}.
Después de completar las operaciones anteriores, el elemento máximo presente en la array es 2.Entrada: arr[] = {7, 17}, K = 2
Salida: 7
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Si X puede ser el elemento máximo en la array arr[] realizando como máximo K operaciones, entonces existe algún valor K (K > X) , que también puede ser el elemento máximo presente en la array arr[] realizando como máximo K división de los elementos de la array.
- Si X no puede ser el elemento máximo en la array A[] realizando como máximo K operaciones, entonces existe algún valor K (K < X) que tampoco puede ser el elemento máximo en la array arr[] realizando en la mayoría de las K divisiones de los elementos de la array.
- Por lo tanto, la idea es utilizar la búsqueda binaria para encontrar el valor sobre el rango [1, INT_MAX ] que puede ser el valor máximo posible después de un máximo de K divisiones.
Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos low y high como 1 y el elemento máximo en la array arr[] respectivamente.
- Iterar hasta que bajo sea menor que alto y realizar los siguientes pasos:
- Encuentre el valor medio del rango [bajo, alto] como medio = (bajo + alto)/2 .
- Inicialice una variable, digamos count , para almacenar el número máximo de divisiones de elementos de array necesarios para que el elemento máximo sea igual a mid .
- Recorra la array dada arr[] y actualice el valor de count como (arr[i] – 1) / mid para contar el número de divisiones requeridas.
- Si el valor de count es como máximo K , actualice el valor de high como mid .
- De lo contrario, actualice el valor de low como (mid + 1) .
- Después de completar los pasos anteriores, imprima el valor de alto como el elemento máximo resultante presente en la array obtenida.
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 check if all array
// elements can be reduced to at
// most mid by at most K splits
int possible(int A[], int N,
int mid, int K)
{
// Stores the number
// of splits required
int count = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Update count
count += (A[i] - 1) / mid;
}
// If possible, return true.
// Otherwise return false
return count <= K;
}
// Function to find the minimum possible
// value of maximum array element that
// can be obtained by at most K splits
int minimumMaximum(int A[], int N, int K)
{
// Set lower and upper limits
int lo = 1;
int hi = *max_element(A, A + N);
int mid;
// Perform Binary Search
while (lo < hi) {
// Calculate mid
mid = (lo + hi) / 2;
// Check if all array elements
// can be reduced to at most
// mid value by at most K splits
if (possible(A, N, mid, K)) {
// Update the value of hi
hi = mid;
}
// Otherwise
else {
// Update the value of lo
lo = mid + 1;
}
}
// Return the minimized maximum
// element in the array
return hi;
}
// Driver Code
int main()
{
int arr[] = { 2, 4, 8, 2 };
int K = 4;
int N = sizeof(arr) / sizeof(arr[0]);
cout << minimumMaximum(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to check if all array
// elements can be reduced to at
// most mid by at most K splits
static boolean possible(int A[], int N,
int mid, int K)
{
// Stores the number
// of splits required
int count = 0;
// Traverse the array arr[]
for(int i = 0; i < N; i++)
{
// Update count
count += (A[i] - 1) / mid;
}
// If possible, return true.
// Otherwise return false
return count <= K;
}
// Function to find the minimum possible
// value of maximum array element that
// can be obtained by at most K splits
static int minimumMaximum(int A[], int N, int K)
{
// Set lower and upper limits
int lo = 1;
Arrays.sort(A);
int hi = A[N - 1];
int mid;
// Perform Binary Search
while (lo < hi)
{
// Calculate mid
mid = (lo + hi) / 2;
// Check if all array elements
// can be reduced to at most
// mid value by at most K splits
if (possible(A, N, mid, K))
{
// Update the value of hi
hi = mid;
}
// Otherwise
else
{
// Update the value of lo
lo = mid + 1;
}
}
// Return the minimized maximum
// element in the array
return hi;
}
// Driver Code
public static void main (String[] args)
{
int arr[] = { 2, 4, 8, 2 };
int K = 4;
int N = arr.length;
System.out.println(minimumMaximum(arr, N, K));
}
}
// This code is contributed by AnkThon
Python3
# Python3 program for the above approach # Function to check if all array # elements can be reduced to at # most mid by at most K splits def possible(A, N, mid, K): # Stores the number # of splits required count = 0 # Traverse the array arr[] for i in range(N): # Update count count += (A[i] - 1) // mid # If possible, return true. # Otherwise return false return count <= K # Function to find the minimum possible # value of maximum array element that # can be obtained by at most K splits def minimumMaximum(A, N, K): # Set lower and upper limits lo = 1 hi = max(A) # Perform Binary Search while (lo < hi): # Calculate mid mid = (lo + hi) // 2 # Check if all array elements # can be reduced to at most # mid value by at most K splits if (possible(A, N, mid, K)): # Update the value of hi hi = mid # Otherwise else: # Update the value of lo lo = mid + 1 # Return the minimized maximum # element in the array return hi # Driver Code if __name__ == '__main__': arr = [ 2, 4, 8, 2 ] K = 4 N = len(arr) print(minimumMaximum(arr, N, K)) # This code is contributed by ipg2016107
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if all array
// elements can be reduced to at
// most mid by at most K splits
static bool possible(int[] A, int N,
int mid, int K)
{
// Stores the number
// of splits required
int count = 0;
// Traverse the array arr[]
for(int i = 0; i < N; i++)
{
// Update count
count += (A[i] - 1) / mid;
}
// If possible, return true.
// Otherwise return false
return count <= K;
}
// Function to find the minimum possible
// value of maximum array element that
// can be obtained by at most K splits
static int minimumMaximum(int[] A, int N, int K)
{
// Set lower and upper limits
int lo = 1;
Array.Sort(A);
int hi = A[N - 1];
int mid;
// Perform Binary Search
while (lo < hi)
{
// Calculate mid
mid = (lo + hi) / 2;
// Check if all array elements
// can be reduced to at most
// mid value by at most K splits
if (possible(A, N, mid, K))
{
// Update the value of hi
hi = mid;
}
// Otherwise
else
{
// Update the value of lo
lo = mid + 1;
}
}
// Return the minimized maximum
// element in the array
return hi;
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 2, 4, 8, 2 };
int K = 4;
int N = arr.Length;
Console.WriteLine(minimumMaximum(arr, N, K));
}
}
// This code is contributed by ukasp
Javascript
<script>
// javascript program for the above approach
// Function to check if all array
// elements can be reduced to at
// most mid by at most K splits
function possible(A, N, mid, K)
{
// Stores the number
// of splits required
var count = 0;
var i;
// Traverse the array arr[]
for (i = 0; i < N; i++) {
// Update count
count += Math.floor((A[i] - 1) / mid);
}
// If possible, return true.
// Otherwise return false
if(count <= K)
return true;
else
return false
}
// Function to find the minimum possible
// value of maximum array element that
// can be obtained by at most K splits
function minimumMaximum(A, N, K)
{
// Set lower and upper limits
var lo = 1;
var hi = Math.max.apply(Math,A);
var mid;
// Perform Binary Search
while (lo < hi) {
// Calculate mid
mid = Math.floor((lo + hi) / 2);
// Check if all array elements
// can be reduced to at most
// mid value by at most K splits
if (possible(A, N, mid, K)) {
// Update the value of hi
hi = mid;
}
// Otherwise
else {
// Update the value of lo
lo = mid + 1;
}
}
// Return the minimized maximum
// element in the array
return hi;
}
// Driver Code
var arr = [2, 4, 8, 2];
var K = 4;
var N = arr.length;
document.write(minimumMaximum(arr, N, K));
// This code is contributed by SURENDRA_GANGWAR.
</script>
Producción:
2
Complejidad temporal: O(N * log M), donde M es el elemento máximo del arreglo .
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