Dada una array arr[] de N elementos y un número entero K, la tarea es realizar como máximo K operaciones en la array. En una sola operación, incremente cualquier elemento por uno de la array. Encuentre maximizar la mediana después de hacer K tal operación.
Ejemplo:
Entrada: arr[] = {1, 3, 4, 5}, K = 3
Salida: 5
Explicación: Aquí sumamos dos en el segundo elemento y uno en el tercer elemento y obtendremos una mediana máxima. Después de la operación k, la array puede convertirse en {1, 5, 5, 5}. Entonces, la mediana máxima que podemos hacer es ( 5 + 5 ) / 2 = 5, porque aquí N es par.Entrada: arr[] = {1, 3, 6, 4, 2}, K = 10
Salida: 7
Acercarse:
- Ordena la array en orden creciente.
- Dado que la mediana es el elemento central de la array que realiza la operación en la mitad izquierda, no tendrá ningún valor porque no aumentará la mediana.
- Realice la operación en la segunda mitad y comience a realizar las operaciones desde el elemento n/2 hasta el final.
- Si N es par, comience a hacer la operación desde el elemento n/2 hasta el final.
- Al usar la búsqueda binaria , verificaremos si cualquier número es posible como mediana o no después de realizar la operación K.
- Si la mediana es posible, buscaremos el siguiente número que sea mayor que la mediana actual calculada. De lo contrario, el último valor posible de la mediana es el resultado requerido.
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 operation can be
// perform or not
bool possible(int arr[], int N,
int mid, int K)
{
int add = 0;
for (int i = N / 2 - (N + 1) % 2;
i < N; ++i) {
if (mid - arr[i] > 0) {
// Number of operation to
// perform s.t. mid is median
add += (mid - arr[i]);
if (add > K)
return false;
}
}
// If mid is median of the array
if (add <= K)
return true;
else
return false;
}
// Function to find max median
// of the array
int findMaxMedian(int arr[], int N,
int K)
{
// Lowest possible median
int low = 1;
int mx = 0;
for (int i = 0; i < N; ++i) {
mx = max(mx, arr[i]);
}
// Highest possible median
long long int high = K + mx;
while (low <= high) {
int mid = (high + low) / 2;
// Checking for mid is possible
// for the median of array after
// doing at most k operation
if (possible(arr, N, mid, K)) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
if (N % 2 == 0) {
if (low - 1 < arr[N / 2]) {
return (arr[N / 2] + low - 1) / 2;
}
}
// Return the max possible ans
return low - 1;
}
// Driver Code
int main()
{
// Given array
int arr[] = { 1, 3, 6 };
// Given number of operation
int K = 10;
// Size of array
int N = sizeof(arr) / sizeof(arr[0]);
// Sort the array
sort(arr, arr + N);
// Function call
cout << findMaxMedian(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to check operation can be
// perform or not
static boolean possible(int arr[], int N,
int mid, int K)
{
int add = 0;
for(int i = N / 2 - (N + 1) % 2;
i < N; ++i)
{
if (mid - arr[i] > 0)
{
// Number of operation to
// perform s.t. mid is median
add += (mid - arr[i]);
if (add > K)
return false;
}
}
// If mid is median of the array
if (add <= K)
return true;
else
return false;
}
// Function to find max median
// of the array
static int findMaxMedian(int arr[], int N,
int K)
{
// Lowest possible median
int low = 1;
int mx = 0;
for(int i = 0; i < N; ++i)
{
mx = Math.max(mx, arr[i]);
}
// Highest possible median
int high = K + mx;
while (low <= high)
{
int mid = (high + low) / 2;
// Checking for mid is possible
// for the median of array after
// doing at most k operation
if (possible(arr, N, mid, K))
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
if (N % 2 == 0)
{
if (low - 1 < arr[N / 2])
{
return (arr[N / 2] + low - 1) / 2;
}
}
// Return the max possible ans
return low - 1;
}
// Driver code
public static void main(String[] args)
{
// Given array
int arr[] = { 1, 3, 6 };
// Given number of operation
int K = 10;
// Size of array
int N = arr.length;
// Sort the array
Arrays.sort(arr);
// Function call
System.out.println(findMaxMedian(arr, N, K));
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach # Function to check operation can be # perform or not def possible(arr, N, mid, K): add = 0 for i in range(N // 2 - (N + 1) % 2, N): if (mid - arr[i] > 0): # Number of operation to # perform s.t. mid is median add += (mid - arr[i]) if (add > K): return False # If mid is median of the array if (add <= K): return True else: return False # Function to find max median # of the array def findMaxMedian(arr, N,K): # Lowest possible median low = 1 mx = 0 for i in range(N): mx = max(mx, arr[i]) # Highest possible median high = K + mx while (low <= high): mid = (high + low) // 2 # Checking for mid is possible # for the median of array after # doing at most k operation if (possible(arr, N, mid, K)): low = mid + 1 else : high = mid - 1 if (N % 2 == 0): if (low - 1 < arr[N // 2]): return (arr[N // 2] + low - 1) // 2 # Return the max possible ans return low - 1 # Driver Code if __name__ == '__main__': # Given array arr = [1, 3, 6] # Given number of operation K = 10 # Size of array N = len(arr) # Sort the array arr = sorted(arr) # Function call print(findMaxMedian(arr, N, K)) # This code is contributed by Mohit Kumar
C#
// C# program for the above approach
using System;
class GFG{
// Function to check operation can be
// perform or not
static bool possible(int []arr, int N,
int mid, int K)
{
int add = 0;
for(int i = N / 2 - (N + 1) % 2;
i < N; ++i)
{
if (mid - arr[i] > 0)
{
// Number of operation to
// perform s.t. mid is median
add += (mid - arr[i]);
if (add > K)
return false;
}
}
// If mid is median of the array
if (add <= K)
return true;
else
return false;
}
// Function to find max median
// of the array
static int findMaxMedian(int []arr, int N,
int K)
{
// Lowest possible median
int low = 1;
int mx = 0;
for(int i = 0; i < N; ++i)
{
mx = Math.Max(mx, arr[i]);
}
// Highest possible median
int high = K + mx;
while (low <= high)
{
int mid = (high + low) / 2;
// Checking for mid is possible
// for the median of array after
// doing at most k operation
if (possible(arr, N, mid, K))
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
if (N % 2 == 0)
{
if (low - 1 < arr[N / 2])
{
return (arr[N / 2] + low - 1) / 2;
}
}
// Return the max possible ans
return low - 1;
}
// Driver code
public static void Main(string[] args)
{
// Given array
int []arr = { 1, 3, 6 };
// Given number of operation
int K = 10;
// Size of array
int N = arr.Length;
// Sort the array
Array.Sort(arr);
// Function call
Console.Write(findMaxMedian(arr, N, K));
}
}
// This code is contributed by rock_cool
Javascript
<script>
// Javascript program for the above approach
// Function to check operation can be
// perform or not
function possible(arr, N, mid, K)
{
let add = 0;
for (let i = parseInt(N / 2, 10) - (N + 1) % 2; i < N; ++i) {
if (mid - arr[i] > 0) {
// Number of operation to
// perform s.t. mid is median
add += (mid - arr[i]);
if (add > K)
return false;
}
}
// If mid is median of the array
if (add <= K)
return true;
else
return false;
}
// Function to find max median
// of the array
function findMaxMedian(arr, N, K)
{
// Lowest possible median
let low = 1;
let mx = 0;
for (let i = 0; i < N; ++i) {
mx = Math.max(mx, arr[i]);
}
// Highest possible median
let high = K + mx;
while (low <= high) {
let mid = parseInt((high + low) / 2, 10);
// Checking for mid is possible
// for the median of array after
// doing at most k operation
if (possible(arr, N, mid, K)) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
if (N % 2 == 0) {
if (low - 1 < arr[parseInt(N / 2)]) {
return parseInt((arr[parseInt(N / 2)] + low - 1) / 2, 10);
}
}
// Return the max possible ans
return low - 1;
}
// Given array
let arr = [ 1, 3, 6 ];
// Given number of operation
let K = 10;
// Size of array
let N = arr.length;
// Sort the array
arr.sort();
// Function call
document.write(findMaxMedian(arr, N, K));
</script>
Producción:
9
Complejidad de tiempo: O(N*log(K + M)) , donde M es el elemento máximo de la array dada.
Espacio Auxiliar: O(1)