Dada una array arr[] que consta de N enteros positivos y un entero positivo K tal que hay N países, cada país tiene arr[i] jugadores, la tarea es encontrar el número máximo de equipos que se pueden formar formando equipos de talla K de manera que cada jugador del equipo sea de un país diferente.
Ejemplos:
Entrada: N = 4, K = 3, arr[] = {4, 3, 5, 3}
Salida: 5
Explicación:
Considere que los países se llaman A, B, C y D. Las formas posibles de formar los equipos son { A, B, C}, {A, C, D}, {A, B, C}, {B, C, D}, {A, C, D} tales que en cada conjunto no haya más de 1 persona de un paísPor lo tanto, el número total de equipos formados es 5.
Entrada: N = 3, K = 2, arr[] = {2, 3, 4}
Salida: 4
Explicación:
Considere que los países se llaman A, B, C y D. Las formas posibles de formar los equipos son {B, C}, {B, C}, {A, C}, ({A, B} o {A, C} o {B, C}) de manera que en cada conjunto no haya más de 1 persona de un país.Por lo tanto, el número total de equipos formados es 4.
Planteamiento: El problema dado se puede resolver utilizando la Búsqueda Binaria , la idea es realizar la Búsqueda Binaria sobre la cantidad de equipos que se pueden formar. Sea esta variable T. Para cada valor de T , compruebe si es posible formar T equipos a partir de la lista dada de jugadores de cada país. Se pueden formar T equipos si la suma del mínimo de arr[i] o T para todos los i sobre el rango [0, N – 1] es mayor que igual a T*K . Siga los pasos a continuación para resolver este problema:
- Defina una función , digamos isPossible(arr, mid, K) para comprobar si se puede formar o no un número medio de equipos.
- Inicialice la variable sum como 0 para almacenar la suma de los elementos de la array .
- Itere sobre un rango [0, N] y realice las siguientes tareas:
- Agregue el valor de un mínimo de mid o arr[i] a la variable sum.
- Si la suma es mayor que igual a mid*K , devuelve true . De lo contrario, devuelve falso .
- Inicialice las variables, digamos lb y ub como 0 y 1e9 como el límite inferior y superior del número de equipos que se pueden formar.
- Iterar durante un ciclo while hasta que lb sea menor que ub y realizar los siguientes pasos:
- Inicialice la variable, digamos mid como el promedio de ub y lb.
- Llame a la función isPossible(arr, mid, K) y si la función devuelve true , verifique la parte superior del rango. De lo contrario, verifique la parte inferior del rango.
- Después de realizar los pasos anteriores, imprima el valor de mid como resultado.
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 if T number of teams
// can be formed or not
bool is_possible(vector<int>& teams,
int T, int k)
{
// Store the sum of array elements
int sum = 0;
// Traverse the array teams[]
for (int i = 0; i < teams.size(); i++) {
sum += min(T, teams[i]);
}
// Required Condition
return (sum >= (T * k));
}
// Function to find the maximum number
// of teams possible
int countOfTeams(vector<int>& teams_list,
int N, int K)
{
// Lower and Upper part of the range
int lb = 0, ub = 1e9;
// Perform the Binary Search
while (lb <= ub) {
// Find the value of mid
int mid = lb + (ub - lb) / 2;
// Perform the Binary Search
if (is_possible(teams_list, mid, K)) {
if (!is_possible(
teams_list, mid + 1, K)) {
return mid;
}
// Otherwise, update the
// search range
else {
lb = mid + 1;
}
}
// Otherwise, update the
// search range
else {
ub = mid - 1;
}
}
return 0;
}
// Driver Code
int main()
{
vector<int> arr = { 2, 3, 4 };
int K = 2;
int N = arr.size();
cout << countOfTeams(arr, N, K);
return 0;
}
Java
// Java program for the above approach
class GFG {
// Function to find if T number of teams
// can be formed or not
public static boolean is_possible(int[] teams, int T, int k)
{
// Store the sum of array elements
int sum = 0;
// Traverse the array teams[]
for (int i = 0; i < teams.length; i++) {
sum += Math.min(T, teams[i]);
}
// Required Condition
return (sum >= (T * k));
}
// Function to find the maximum number
// of teams possible
public static int countOfTeams(int[] teams_list, int N, int K)
{
// Lower and Upper part of the range
int lb = 0;
double ub = 1e9;
// Perform the Binary Search
while (lb <= ub) {
// Find the value of mid
int mid = lb + (int) (ub - lb) / 2;
// Perform the Binary Search
if (is_possible(teams_list, mid, K)) {
if (!is_possible(teams_list, mid + 1, K)) {
return mid;
}
// Otherwise, update the
// search range
else {
lb = mid + 1;
}
}
// Otherwise, update the
// search range
else {
ub = mid - 1;
}
}
return 0;
}
// Driver Code
public static void main(String args[]) {
int[] arr = { 2, 3, 4 };
int K = 2;
int N = arr.length;
System.out.println(countOfTeams(arr, N, K));
}
}
// This code is contributed by _saurabh_jaiswal.
Python3
# Python 3 program for the above approach # Function to find if T number of teams # can be formed or not def is_possible(teams, T, k): # Store the sum of array elements sum = 0 # Traverse the array teams[] for i in range(len(teams)): sum += min(T, teams[i]) # Required Condition return (sum >= (T * k)) # Function to find the maximum number # of teams possible def countOfTeams(teams_list, N, K): # Lower and Upper part of the range lb = 0 ub = 1000000000 # Perform the Binary Search while (lb <= ub): # Find the value of mid mid = lb + (ub - lb) // 2 # Perform the Binary Search if (is_possible(teams_list, mid, K)): if (is_possible(teams_list, mid + 1, K)==False): return mid # Otherwise, update the # search range else: lb = mid + 1 # Otherwise, update the # search range else: ub = mid - 1 return 0 # Driver Code if __name__ == '__main__': arr = [2, 3, 4] K = 2 N = len(arr) print(countOfTeams(arr, N, K)) # This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
class GFG{
// Function to find if T number of teams
// can be formed or not
public static bool is_possible(int[] teams,
int T, int k)
{
// Store the sum of array elements
int sum = 0;
// Traverse the array teams[]
for(int i = 0; i < teams.Length; i++)
{
sum += Math.Min(T, teams[i]);
}
// Required Condition
return (sum >= (T * k));
}
// Function to find the maximum number
// of teams possible
public static int countOfTeams(int[] teams_list,
int N, int K)
{
// Lower and Upper part of the range
int lb = 0;
double ub = 1e9;
// Perform the Binary Search
while (lb <= ub)
{
// Find the value of mid
int mid = lb + (int) (ub - lb) / 2;
// Perform the Binary Search
if (is_possible(teams_list, mid, K))
{
if (!is_possible(teams_list, mid + 1, K))
{
return mid;
}
// Otherwise, update the
// search range
else
{
lb = mid + 1;
}
}
// Otherwise, update the
// search range
else
{
ub = mid - 1;
}
}
return 0;
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 2, 3, 4 };
int K = 2;
int N = arr.Length;
Console.WriteLine(countOfTeams(arr, N, K));
}
}
// This code is contributed by code_hunt
Javascript
<script>
// JavaScript program for the above approach
// Function to find if T number of teams
// can be formed or not
function is_possible(teams, T, k) {
// Store the sum of array elements
let sum = 0;
// Traverse the array teams[]
for (let i = 0; i < teams.length; i++) {
sum += Math.min(T, teams[i]);
}
// Required Condition
return sum >= T * k;
}
// Function to find the maximum number
// of teams possible
function countOfTeams(teams_list, N, K) {
// Lower and Upper part of the range
let lb = 0,
ub = 1e9;
// Perform the Binary Search
while (lb <= ub) {
// Find the value of mid
let mid = Math.floor(lb + (ub - lb) / 2);
// Perform the Binary Search
if (is_possible(teams_list, mid, K)) {
if (!is_possible(teams_list, mid + 1, K)) {
return mid;
}
// Otherwise, update the
// search range
else {
lb = mid + 1;
}
}
// Otherwise, update the
// search range
else {
ub = mid - 1;
}
}
return 0;
}
// Driver Code
let arr = [2, 3, 4];
let K = 2;
let N = arr.length;
document.write(countOfTeams(arr, N, K));
</script>
4
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por suman_1729 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA