Dado un número entero, P denota el número de chocolates y una array a[] donde ai denota el tipo de i -ésimo chocolate. Hay N personas que quieren comer chocolate todos los días. Encuentre el número máximo de días consecutivos durante los cuales N personas pueden comer chocolates considerando las siguientes condiciones:
- Cada una de las N personas debe comer exactamente un chocolate en un día en particular.
- Una sola persona puede comer chocolate del mismo tipo solo durante todos los días.
Ejemplos:
Entrada: N = 4, P = 10, arr[] = {1, 5, 2, 1, 1, 1, 2, 5, 7, 2}
Salida: 2
Explicación: Los chocolates se pueden asignar de la siguiente manera:
Persona 1: Tipo 1
Persona 2: Tipo 1
Persona 3: Tipo 2
Persona 4: Tipo 5
De esta manera, hay suficientes chocolates para que cada persona coma un chocolate durante dos días consecutivos. Ninguna otra distribución posible de chocolates puede hacer que las personas coman los chocolates por más de 2 días.Entrada: N = 3, P = 10, arr[] = {1, 2, 2, 1, 1, 3, 3, 3, 2, 4}
Salida: 3
Explicación: Los chocolates se pueden distribuir de la siguiente manera:
Persona 1: Tipo 1
Persona 2: Tipo 2
Persona 3: Tipo 3
De esta manera, las 3 personas pueden comer su respectivo tipo de chocolates asignados durante tres días.
Enfoque: siga los pasos a continuación para resolver el problema:
- El número mínimo de días durante los cuales es posible repartir los chocolates es 0 y el número máximo es P .
- Entonces, para cada número X en este rango, verifique si es posible repartir chocolates a cada persona durante X días.
- Para todas esas X, encuentre el máximo.
- Ahora, utilizando la búsqueda binaria , verifique todos los números en el rango de 0 a P.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Stores the frequency of
// each type of chocolate
map<int, int> mp;
int N, P;
// Function to check if chocolates
// can be eaten for 'mid' no. of days
bool helper(int mid)
{
int cnt = 0;
for (auto i : mp) {
int temp = i.second;
while (temp >= mid) {
temp -= mid;
cnt++;
}
}
// If cnt exceeds N,
// return true
return cnt >= N;
}
// Function to find the maximum
// number of days for which
// chocolates can be eaten
int findMaximumDays(int arr[])
{
// Store the frequency
// of each type of chocolate
for (int i = 0; i < P; i++) {
mp[arr[i]]++;
}
// Initialize start and end
// with 0 and P respectively
int start = 0, end = P, ans = 0;
while (start <= end) {
// Calculate mid
int mid = start
+ ((end - start) / 2);
// Check if chocolates can be
// distributed for mid days
if (mid != 0 and helper(mid)) {
ans = mid;
// Check if chocolates can
// be distributed for more
// than mid consecutive days
start = mid + 1;
}
else if (mid == 0) {
start = mid + 1;
}
else {
end = mid - 1;
}
}
return ans;
}
// Driver code
int main()
{
N = 3, P = 10;
int arr[] = { 1, 2, 2, 1, 1,
3, 3, 3, 2, 4 };
// Function call
cout << findMaximumDays(arr);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Stores the frequency of
// each type of chocolate
static HashMap<Integer,
Integer> mp = new HashMap<Integer,
Integer>();
static int N, P;
// Function to check if chocolates
// can be eaten for 'mid' no. of days
static boolean helper(int mid)
{
int cnt = 0;
for(Map.Entry<Integer, Integer> i : mp.entrySet())
{
int temp = i.getValue();
while (temp >= mid)
{
temp -= mid;
cnt++;
}
}
// If cnt exceeds N,
// return true
return cnt >= N;
}
// Function to find the maximum
// number of days for which
// chocolates can be eaten
static int findMaximumDays(int arr[])
{
// Store the frequency
// of each type of chocolate
for(int i = 0; i < P; i++)
{
if (mp.containsKey(arr[i]))
{
mp.put(arr[i], mp.get(arr[i]) + 1);
}
else
{
mp.put(arr[i], 1);
}
}
// Initialize start and end
// with 0 and P respectively
int start = 0, end = P, ans = 0;
while (start <= end)
{
// Calculate mid
int mid = start +
((end - start) / 2);
// Check if chocolates can be
// distributed for mid days
if (mid != 0 && helper(mid))
{
ans = mid;
// Check if chocolates can
// be distributed for more
// than mid consecutive days
start = mid + 1;
}
else if (mid == 0)
{
start = mid + 1;
}
else
{
end = mid - 1;
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
N = 3;
P = 10;
int arr[] = { 1, 2, 2, 1, 1,
3, 3, 3, 2, 4 };
// Function call
System.out.print(findMaximumDays(arr));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to implement
# the above approach
# Stores the frequency of
# each type of chocolate
mp = {}
N, P = 0, 0
# Function to check if chocolates
# can be eaten for 'mid' no. of days
def helper(mid):
cnt = 0;
for i in mp:
temp = mp[i]
while (temp >= mid):
temp -= mid
cnt += 1
# If cnt exceeds N,
# return true
return cnt >= N
# Function to find the maximum
# number of days for which
# chocolates can be eaten
def findMaximumDays(arr):
# Store the frequency
# of each type of chocolate
for i in range(P):
mp[arr[i]] = mp.get(arr[i], 0) + 1
# Initialize start and end
# with 0 and P respectively
start = 0
end = P
ans = 0
while (start <= end):
# Calculate mid
mid = start + ((end - start) // 2)
# Check if chocolates can be
# distributed for mid days
if (mid != 0 and helper(mid)):
ans = mid
# Check if chocolates can
# be distributed for more
# than mid consecutive days
start = mid + 1
elif (mid == 0):
start = mid + 1
else:
end = mid - 1
return ans
# Driver code
if __name__ == '__main__':
N = 3
P = 10
arr = [ 1, 2, 2, 1, 1,
3, 3, 3, 2, 4 ]
# Function call
print(findMaximumDays(arr))
# This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Stores the frequency of
// each type of chocolate
static Dictionary<int,
int> mp = new Dictionary<int,
int>();
static int N, P;
// Function to check if
// chocolates can be eaten
// for 'mid' no. of days
static bool helper(int mid)
{
int cnt = 0;
foreach(KeyValuePair<int,
int> i in mp)
{
int temp = i.Value;
while (temp >= mid)
{
temp -= mid;
cnt++;
}
}
// If cnt exceeds N,
// return true
return cnt >= N;
}
// Function to find the maximum
// number of days for which
// chocolates can be eaten
static int findMaximumDays(int []arr)
{
// Store the frequency
// of each type of chocolate
for(int i = 0; i < P; i++)
{
if (mp.ContainsKey(arr[i]))
{
mp[arr[i]] = mp[arr[i]] + 1;
}
else
{
mp.Add(arr[i], 1);
}
}
// Initialize start and end
// with 0 and P respectively
int start = 0, end = P, ans = 0;
while (start <= end)
{
// Calculate mid
int mid = start +
((end - start) / 2);
// Check if chocolates can be
// distributed for mid days
if (mid != 0 && helper(mid))
{
ans = mid;
// Check if chocolates can
// be distributed for more
// than mid consecutive days
start = mid + 1;
}
else if (mid == 0)
{
start = mid + 1;
}
else
{
end = mid - 1;
}
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
N = 3;
P = 10;
int []arr = {1, 2, 2, 1, 1,
3, 3, 3, 2, 4};
// Function call
Console.Write(findMaximumDays(arr));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to implement
// the above approach
// Stores the frequency of
// each type of chocolate
var mp = new Map();
var N, P;
// Function to check if chocolates
// can be eaten for 'mid' no. of days
function helper(mid)
{
var cnt = 0;
mp.forEach((value,) => {
var temp = value;
while (temp >= mid) {
temp -= mid;
cnt++;
}
});
// If cnt exceeds N,
// return true
return cnt >= N;
}
// Function to find the maximum
// number of days for which
// chocolates can be eaten
function findMaximumDays(arr)
{
// Store the frequency
// of each type of chocolate
for (var i = 0; i < P; i++) {
if(mp.has(arr[i]))
mp.set(arr[i], mp.get(arr[i])+1)
else
mp.set(arr[i], 1);
}
// Initialize start and end
// with 0 and P respectively
var start = 0, end = P, ans = 0;
while (start <= end) {
// Calculate mid
var mid = start
+ parseInt((end - start) / 2);
// Check if chocolates can be
// distributed for mid days
if (mid != 0 && helper(mid)) {
ans = mid;
// Check if chocolates can
// be distributed for more
// than mid consecutive days
start = mid + 1;
}
else if (mid == 0) {
start = mid + 1;
}
else {
end = mid - 1;
}
}
return ans;
}
// Driver code
N = 3, P = 10;
var arr = [1, 2, 2, 1, 1,
3, 3, 3, 2, 4 ];
// Function call
document.write( findMaximumDays(arr));
</script>
Producción
3
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por vashisthamadhur2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA