Dado un número entero N que denota el número de cartas en una baraja específica y una array arr[] de tamaño N donde i -ésimo elemento denota la frecuencia del i -ésimo tipo de carta. También dado K Jokers. La tarea es encontrar el máximo de barajas válidas posibles con los datos dados.
Una baraja válida debe cumplir una de las dos condiciones mencionadas:
1. Una baraja que contenga exactamente una carta de cada tipo y sin comodines.
2. Una baraja que contiene exactamente una carta de cada tipo excepto una, y exactamente un comodín.
Ejemplos :
Entrada : N = 2, arr[] = {10, 15}, K = 3
Salida : 13
Explicación : A continuación se muestran las formas en que se hacen 13 barajas:
10 barajas de tipo {1, 2}
3 barajas de tipo {J , 2}
Por lo tanto, el número máximo posible de barajas es 10 + 3 = 13 barajas.Entrada : N = 3, arr[] = {1, 2, 3}, K = 4
Salida : 3
Explicación : A continuación se muestran las formas en que se hacen 13 barajas:
1 baraja de tipo {1, 2, 3}
1 baraja de tipo {J, 2, 3}
1 mazo de tipo {J, 2, 3}
Por lo tanto, el número máximo posible de mazos es 1+1+1 = 3 mazos.
Enfoque : el problema dado se puede resolver utilizando el enfoque codicioso y el algoritmo de búsqueda binaria . Siga los pasos a continuación para resolver el problema dado.
- Ordene la array dada arr[] en orden no decreciente.
- La búsqueda binaria se puede aplicar en la respuesta para obtener el valor máximo.
- Inicialice dos variables, digamos, L = 0 y R = max_element (arr) + K + 1 que definirán el rango inicial de respuesta a descubrir.
- Iterar mientras L +1 < R
- Inicialice una variable, digamos mid = (L + R)/2 para realizar un seguimiento del elemento central en el rango en cada iteración.
- Use una variable say, need = 0 para contar las tarjetas adicionales necesarias para el elemento intermedio actual.
- iterar toda la array arr[] con la variable i :
- if arr[i] < mid set need = necesidad + arr[i] – mid.
- si necesita <= mid y necesita <= k , establezca L = mid .
- de lo contrario establecer R = mid .
- Por último, la respuesta final se almacenará en L , por lo tanto, devuelva L como respuesta.
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 maximum possible decks
// with given frequency of cards and
// number of jokers
int maximumCardDecks(int arr[], int n, int k)
{
// Sort the whole array
sort(arr, arr + n);
// Store the binary search range
int L = 0;
int R = arr[n - 1] + k + 1;
// Do a binary search on range
while (L + 1 < R) {
// Compute the mid value of the current
// binary search range
int mid = (L + R) / 2;
// Store extra needed
int need = 0;
// Iterate over the total cards and
// compute variable need.
for (int i = 0; i < n; i++) {
if (arr[i] < mid) {
need += mid - arr[i];
}
}
if (need <= mid && need <= k) {
L = mid;
}
else {
R = mid;
}
}
return L;
}
// Driver Code
int main()
{
int N = 3, K = 4;
int arr[] = { 1, 2, 3 };
cout << maximumCardDecks(arr, N, K);
}
Java
// Java program for the above approach
import java.io.*;
import java.util.Arrays;
class GFG
{
// Function to find maximum possible decks
// with given frequency of cards and
// number of jokers
static int maximumCardDecks(int arr[], int n, int k)
{
// Sort the whole array
Arrays.sort(arr);
// Store the binary search range
int L = 0;
int R = arr[n - 1] + k + 1;
// Do a binary search on range
while (L + 1 < R)
{
// Compute the mid value of the current
// binary search range
int mid = (L + R) / 2;
// Store extra needed
int need = 0;
// Iterate over the total cards and
// compute variable need.
for (int i = 0; i < n; i++) {
if (arr[i] < mid) {
need += mid - arr[i];
}
}
if (need <= mid && need <= k) {
L = mid;
}
else {
R = mid;
}
}
return L;
}
// Driver Code
public static void main (String[] args)
{
int N = 3, K = 4;
int arr[] = { 1, 2, 3 };
System.out.print(maximumCardDecks(arr, N, K));
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python Program to implement # the above approach # Function to find maximum possible decks # with given frequency of cards and # number of jokers def maximumCardDecks(arr, n, k): # Sort the whole array arr.sort() # Store the binary search range L = 0 R = arr[n - 1] + k + 1 # Do a binary search on range while (L + 1 < R) : # Compute the mid value of the current # binary search range mid = (L + R) // 2 # Store extra needed need = 0 # Iterate over the total cards and # compute variable need. for i in range(n): if (arr[i] < mid): need += mid - arr[i] if (need <= mid and need <= k): L = mid else: R = mid return L # Driver Code N = 3 K = 4 arr = [1, 2, 3] print(maximumCardDecks(arr, N, K)) # This code is contributed by gfgking
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find maximum possible decks
// with given frequency of cards and
// number of jokers
static int maximumCardDecks(int []arr, int n, int k)
{
// Sort the whole array
Array.Sort(arr);
// Store the binary search range
int L = 0;
int R = arr[n - 1] + k + 1;
// Do a binary search on range
while (L + 1 < R)
{
// Compute the mid value of the current
// binary search range
int mid = (L + R) / 2;
// Store extra needed
int need = 0;
// Iterate over the total cards and
// compute variable need.
for (int i = 0; i < n; i++) {
if (arr[i] < mid) {
need += mid - arr[i];
}
}
if (need <= mid && need <= k) {
L = mid;
}
else {
R = mid;
}
}
return L;
}
// Driver Code
public static void Main (String[] args)
{
int N = 3, K = 4;
int []arr = { 1, 2, 3 };
Console.Write(maximumCardDecks(arr, N, K));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find maximum possible decks
// with given frequency of cards and
// number of jokers
function maximumCardDecks(arr, n, k)
{
// Sort the whole array
arr.sort(function (a, b) { return a - b })
// Store the binary search range
let L = 0;
let R = arr[n - 1] + k + 1;
// Do a binary search on range
while (L + 1 < R) {
// Compute the mid value of the current
// binary search range
let mid = (L + R) / 2;
// Store extra needed
let need = 0;
// Iterate over the total cards and
// compute variable need.
for (let i = 0; i < n; i++) {
if (arr[i] < mid) {
need += mid - arr[i];
}
}
if (need <= mid && need <= k) {
L = mid;
}
else {
R = mid;
}
}
return L;
}
// Driver Code
let N = 3, K = 4;
let arr = [1, 2, 3];
document.write(maximumCardDecks(arr, N, K));
// This code is contributed by Potta Lokesh
</script>
3
Complejidad de tiempo : O (N (log (N) + log (M + K)), donde M es el elemento máximo de la array.
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