Dada una array arr[] y dos enteros positivos K y C , la tarea es maximizar el K -ésimo elemento máximo obtenido después de dividir un elemento de array arr[] en dos partes (no necesariamente un número entero) C número de veces. Imprime -1 si no existe el K -ésimo elemento máximo.
Nota: Es obligatorio realizar la operación de división hasta que el tamaño de la array arr[] sea ≥ K .
Ejemplos:
Entrada: arr[] = {5, 8}, K = 1, C = 1
Salida: 8.0
Explicación: No es necesario realizar ninguna operación. La array final será {8, 5} Por lo tanto, 8.0 es el valor máximo alcanzable.Entrada: arr[] = {5, 9}, K = 3, C = 1
Salida: 4,5
Explicación: el valor 9 se puede dividir en 4,5 y 4,5. La array final será {5, 4,5, 4,5} donde el tercer valor es 4,5, que es el máximo alcanzable.
Enfoque: el problema dado se puede resolver utilizando la búsqueda binaria en la respuesta. Siga los pasos a continuación para resolver el problema dado.
- Inicialice dos variables, digamos bajo y alto como 0 y 10 9 respectivamente que representan el rango donde se puede realizar la búsqueda binaria.
- Realice la búsqueda binaria siguiendo los siguientes pasos:
- Encuentre el valor de mid como (low + high)*0.5 .
- Recorra la array dada arr[] y almacene el recuento de elementos que es al menos el valor de mid en la variable, digamos A y también encuentre el número de operaciones realizadas en la variable, digamos B.
- Si el valor de (A ≥ K) y (B + C ≥ K) , actualice el valor de bajo como medio . De lo contrario, actualice el valor de alto como medio .
- Después de completar los pasos anteriores, el valor almacenado en la variable low es el K -ésimo elemento máximo maximizado resultante .
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 find the K-th maximum
// element after upto C operations
double maxKth(int arr[], int N,
int C, int K)
{
// Check for the base case
if (N + C < K) {
return -1;
}
// Stores the count iterations of BS
int iter = 300;
// Create the left and right bounds
// of binary search
double l = 0, r = 1000000000.0;
// Perform binary search
while (iter--) {
// Find the value of mid
double mid = (l + r) * 0.5;
double a = 0;
double b = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
a += int((double)arr[i] / mid);
if ((double)arr[i] >= mid) {
b++;
}
}
// Update the ranges
if (a >= K && b + C >= K) {
l = mid;
}
else {
r = mid;
}
}
// Return the maximum value obtained
return l;
}
// Driver Code
int main()
{
int arr[] = { 5, 8 };
int K = 1, C = 1;
int N = sizeof(arr) / sizeof(arr[0]);
cout << maxKth(arr, N, C, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG
{
// Function to find the K-th maximum
// element after upto C operations
static double maxKth(int arr[], int N, int C, int K)
{
// Check for the base case
if (N + C < K) {
return -1;
}
// Stores the count iterations of BS
int iter = 300;
// Create the left and right bounds
// of binary search
double l = 0, r = 1000000000.0;
// Perform binary search
while (iter-- > 0) {
// Find the value of mid
double mid = (l + r) * 0.5;
double a = 0;
double b = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
a += (int)((double)arr[i] / mid);
if ((double)arr[i] >= mid) {
b++;
}
}
// Update the ranges
if (a >= K && b + C >= K) {
l = mid;
}
else {
r = mid;
}
}
// Return the maximum value obtained
return l;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 5, 8 };
int K = 1, C = 1;
int N = arr.length;
System.out.println(maxKth(arr, N, C, K));
}
}
// This code is contributed by Dharanendra L V.
Python3
# Python Program to implement # the above approach # Function to find the K-th maximum # element after upto C operations def maxKth(arr, N, C, K): # Check for the base case if (N + C < K): return -1 # Stores the count iterations of BS iter = 300 # Create the left and right bounds # of binary search l = 0 r = 1000000000.0 # Perform binary search while (iter): iter = iter - 1 # Find the value of mid mid = (l + r) * 0.5 a = 0 b = 0 # Traverse the array for i in range(N) : a += arr[i] // mid if (arr[i] >= mid) : b += 1 # Update the ranges if (a >= K and b + C >= K) : l = mid else : r = mid # Return the maximum value obtained return int(l) # Driver Code arr = [5, 8] K = 1 C = 1 N = len(arr) print(maxKth(arr, N, C, K)) # This code is contributed by Saurabh Jaiswal
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find the K-th maximum
// element after upto C operations
static double maxKth(int []arr, int N, int C, int K)
{
// Check for the base case
if (N + C < K) {
return -1;
}
// Stores the count iterations of BS
int iter = 300;
// Create the left and right bounds
// of binary search
double l = 0, r = 1000000000.0;
// Perform binary search
while (iter-- > 0) {
// Find the value of mid
double mid = (l + r) * 0.5;
double a = 0;
double b = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
a += (int)((double)arr[i] / mid);
if ((double)arr[i] >= mid) {
b++;
}
}
// Update the ranges
if (a >= K && b + C >= K) {
l = mid;
}
else {
r = mid;
}
}
// Return the maximum value obtained
return l;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 5, 8 };
int K = 1, C = 1;
int N = arr.Length;
Console.Write(maxKth(arr, N, C, K));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the K-th maximum
// element after upto C operations
function maxKth(arr, N,
C, K)
{
// Check for the base case
if (N + C < K) {
return -1;
}
// Stores the count iterations of BS
let iter = 300;
// Create the left and right bounds
// of binary search
let l = 0, r = 1000000000.0;
// Perform binary search
while (iter--) {
// Find the value of mid
let mid = (l + r) * 0.5;
let a = 0;
let b = 0;
// Traverse the array
for (let i = 0; i < N; i++) {
a += Math.floor(arr[i] / mid);
if (arr[i] >= mid) {
b++;
}
}
// Update the ranges
if (a >= K && b + C >= K) {
l = mid;
}
else {
r = mid;
}
}
// Return the maximum value obtained
return l;
}
// Driver Code
let arr = [5, 8];
let K = 1, C = 1;
let N = arr.length;
document.write(maxKth(arr, N, C, K));
// This code is contributed by Potta Lokesh
</script>
Producción:
8
Complejidad de tiempo: O(N*log M)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA