Dadas N cubetas, cada una de las cuales contiene A[i] elementos. Dados los K recorridos dentro de los cuales se deben entregar todos los artículos. Se permite tomar artículos de un solo balde en 1 recorrido. La tarea es indicar la cantidad mínima de artículos que se deben entregar por recorrido para que todos los artículos se puedan entregar dentro de K recorridos.
Condiciones: K >= N
Ejemplos :
Input :
N = 5
A[] = { 1, 3, 5, 7, 9 }
K = 10
Output : 3
By delivering 3 items at a time,
Number of tours required for bucket 1 = 1
Number of tours required for bucket 2 = 1
Number of tours required for bucket 3 = 2
Number of tours required for bucket 4 = 3
Number of tours required for bucket 5 = 3
Total number of tours = 10
Input :
N = 10
A = 1, 4, 9, 16, 25, 36, 49, 64, 81, 100
k = 50
Output : 9
Enfoque : Se necesita encontrar el número mínimo de artículos por entrega. Entonces, la idea es iterar desde 1 hasta el valor máximo de los artículos en un depósito y calcular la cantidad de recorridos necesarios para cada depósito y encontrar el número total de recorridos para la entrega completa. El primero de estos valores con recorridos menores o iguales a K da el número requerido.
A continuación se muestra la implementación de la idea anterior:
C++
//C++ program to find the minimum numbers of tours required
#include <bits/stdc++.h>
using namespace std;
int getMin(int N,int A[],int k)
{
//Iterating through each possible
// value of minimum Items
int maximum=0,tours=0;
for(int i=0;i<N;i++)
maximum=max(maximum,A[i]);
for(int i=1;i<maximum+1;i++)
{
tours=0;
for(int j=0;j<N;j++)
{
if(A[j]%i==0)//perfecctly Divisible
{
tours+=A[j]/i;
}else{
// Not Perfectly Divisible means required
// tours are Floor Division + 1
tours += floor(A[j]/i) + 1;
}
}
if(tours<=k)
{
// Return First Feasible Value found,
// since it is also the minimum
return i;
}
}
return -1;
}
//Driver code
int main()
{
int a[]={1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
int n=sizeof(a)/sizeof(a[0]);
int k=50;
if(getMin(n,a,k)==-1)
cout<<"Not Possible";
else
cout<<getMin(n,a,k);
}
//This code is contributed by Mohit kumar 29
Java
// Java program to find the minimum numbers of tours required
import java.util.*;
class solution
{
static int getMin(int N,int A[],int k)
{
//Iterating through each possible
// value of minimum Items
int maximum=0,tours=0;
for(int i=0;i<N;i++)
maximum=Math.max(maximum,A[i]);
for(int i=1;i<maximum+1;i++)
{
tours=0;
for(int j=0;j<N;j++)
{
if(A[j]%i==0)//perfecctly Divisible
{
tours+=A[j]/i;
}else{
// Not Perfectly Divisible means required
// tours are Floor Division + 1
tours += Math.floor(A[j]/i) + 1;
}
}
if(tours<=k)
{
// Return First Feasible Value found,
// since it is also the minimum
return i;
}
}
return -1;
}
//Driver code
public static void main(String args[])
{
int a[]={1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
int n=a.length;
int k=50;
if(getMin(n,a,k)==-1)
System.out.println("Not Possible");
else
System.out.println(getMin(n,a,k));
}
}
//This code is contributed by
// Surendra_Gangwar
Python3
# Python3 program to find minimum numbers of # tours required def getMin(N, A, k): # Iterating through each possible # value of minimum Items for i in range(1, max(A)+1): tours = 0 for j in range(0, len(A)): if(A[j]% i == 0):# Perfectly Divisible tours += A[j]/i else: # Not Perfectly Divisible means required # tours are Floor Division + 1 tours += A[j]//i + 1 if(tours <= k): # Return First Feasible Value found, # since it is also the minimum return i return "Not Possible" # Driver Code N = 10 A = [1, 4, 9, 16, 25, 36, 49, 64, 81, 100] k = 50 print(getMin(N, A, k))
C#
// C# program to find the minimum
// numbers of tours required
using System;
class GFG
{
static int getMin(int N, int [] A, int k)
{
// Iterating through each possible
// value of minimum Items
int maximum = 0,tours = 0;
for(int i = 0; i < N; i++)
maximum = Math.Max(maximum, A[i]);
for(int i = 1; i < maximum + 1; i++)
{
tours = 0;
for(int j = 0; j < N; j++)
{
if(A[j] % i == 0)// perfecctly Divisible
{
tours += A[j] /i;
}
else
{
// Not Perfectly Divisible means required
// tours are Floor Division + 1
tours += (int)Math.Floor(A[j] / (i * 1.0)) + 1;
}
}
if(tours <= k)
{
// Return First Feasible Value found,
// since it is also the minimum
return i;
}
}
return -1;
}
// Driver code
public static void Main()
{
int []a = {1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
int n = 10;
int k = 50;
if(getMin(n, a, k) == -1)
Console.WriteLine("Not Possible");
else
Console.WriteLine(getMin(n, a, k));
}
}
// This code is contributed by
// Mohit kumar
PHP
<?php
// PHP program to find the minimum number
// of tours required
function getMin($N, $A, $k)
{
// Iterating through each possible
// value of minimum Items
$maximum = 0;
$tours = 0;
for($i = 0; $i < $N; $i++)
$maximum = max($maximum, $A[$i]);
for($i = 1; $i < $maximum + 1; $i++)
{
$tours = 0;
for($j = 0; $j < $N; $j++)
{
if($A[$j] % $i == 0) // perfectly Divisible
{
$tours += $A[$j] / $i;
}
else
{
// Not Perfectly Divisible means required
// tours are Floor Division + 1
$tours += floor($A[$j] / $i) + 1;
}
}
if($tours <= $k)
{
// Return First Feasible Value found,
// since it is also the minimum
return $i;
}
}
return -1;
}
// Driver code
$a = array(1, 4, 9, 16, 25, 36,
49, 64, 81, 100);
$n = sizeof($a);
$k = 50;
if(getMin($n, $a, $k) == -1)
echo "Not Possible";
else
echo getMin($n, $a, $k);
// This code is contributed by ihritik
?>
Javascript
<script>
// Javascript program to find the minimum numbers of tours required
function getMin(N,A,k)
{
//Iterating through each possible
// value of minimum Items
let maximum = 0, tours = 0;
for(let i = 0; i < N; i++)
maximum=Math.max(maximum, A[i]);
for(let i = 1; i < maximum + 1; i++)
{
tours = 0;
for(let j = 0; j < N; j++)
{
if(A[j] % i == 0)//perfecctly Divisible
{
tours+=Math.floor(A[j]/i);
}else{
// Not Perfectly Divisible means required
// tours are Floor Division + 1
tours += Math.floor(A[j]/i) + 1;
}
}
if(tours<=k)
{
// Return First Feasible Value found,
// since it is also the minimum
return i;
}
}
return -1;
}
//Driver code
let a = [1, 4, 9, 16, 25, 36, 49, 64, 81, 100];
let n = a.length;
let k = 50;
if(getMin(n, a, k) == -1)
document.write("Not Possible<br>");
else
document.write(getMin(n, a, k));
// This code is contributed by patel2127
</script>
Producción
9
Complejidad de tiempo: O (N * MAX) donde N es el número total de elementos en la array y MAX es el elemento máximo en la array.
Espacio Auxiliar: O(1)
Enfoque eficiente:
La cantidad máxima de elementos que se pueden entregar por recorrido es el elemento máximo en la array. Con esta información, podemos usar la búsqueda binaria donde inicialmente bajo = 1 y alto = elemento máximo + 1 y encontrar la cantidad de recorridos requeridos cuando el número de artículos que se deben entregar por recorrido es medio donde medio = bajo + (alto – bajo)/ 2. Si es menor o igual a k, entonces actualizamos la respuesta a medio y establecemos alto = medio, de lo contrario, actualizamos bajo a medio.
A continuación se muestra la implementación del enfoque anterior:
C++
//C++ program to find the minimum numbers of tours required
#include<bits/stdc++.h>
using namespace std;
int reqdTours(vector<int> a,int cur)
{
int cur_tours = 0;
int n=(int)a.size();
for(int i=0; i< n;i++ )
cur_tours += ( a[i]+cur-1)/cur;
return cur_tours;
}
int getMin(vector<int>a , int k)
{
int maxm=0;
int n=(int)a.size();
// find the maximum element in array
for(int i=0;i<n;i++)
maxm= max(a[i],maxm);
int low = 1 , high = maxm+1;
int ans = -1;
// binary search to find the required number of
// tours
while(low+1<high)
{
int mid = low + (high-low)/2;
// reqdTours find the number of tours
// required when number of items
// needed to be delivered per tour is mid
if(reqdTours(a,mid)<=k)
{
high = mid;
ans = high;
}
else
{
low = mid;
}
}
return ans;
}
// Driver Code
int main()
{
vector<int> a={1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
int k=50;
if(getMin(a,k)==-1)
cout<<"Not Possible";
else
cout<<getMin(a,k);
}
Java
// Java program to find the minimum numbers of tours
// required
import java.io.*;
import java.util.*;
class GFG {
static int reqdTours(int[] a, int cur)
{
int cur_tours = 0;
int n = a.length;
for (int i = 0; i < n; i++)
cur_tours += (a[i] + cur - 1) / cur;
return cur_tours;
}
static int getMin(int[] a, int k)
{
int maxm = 0;
int n = a.length;
// find the maximum element in array
for (int i = 0; i < n; i++)
maxm = Math.max(a[i], maxm);
int low = 1, high = maxm + 1;
int ans = -1;
// binary search to find the required number of
// tours
while (low + 1 < high) {
int mid = low + (high - low) / 2;
// reqdTours find the number of tours
// required when number of items
// needed to be delivered per tour is mid
if (reqdTours(a, mid) <= k) {
high = mid;
ans = high;
}
else {
low = mid;
}
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int[] a = { 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 };
int k = 50;
if (getMin(a, k) == -1)
System.out.println("Not Possible");
else
System.out.println(getMin(a, k));
}
}
// This code is contributed by Karandeep1234
Python3
#Python3 program to find the minimum numbers of tours required
def reqdTours(a, cur):
cur_tours = 0
n=len(a)
for i in range(n):
cur_tours += ( a[i]+cur-1)//cur
return cur_tours
def getMin(a, k):
maxm=0
n=len(a)
# find the maximum element in array
for i in range(n):
maxm= max(a[i],maxm)
low = 1 ; high = maxm+1
ans = -1
# binary search to find the required number of
# tours
while(low+1<high):
mid = low + (high-low)//2
# reqdTours find the number of tours
# required when number of items
# needed to be delivered per tour is mid
if(reqdTours(a,mid)<=k):
high = mid
ans = high
else:
low = mid
return ans
# Driver Code
if __name__ == '__main__':
a=[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
k=50
if(getMin(a,k)==-1):
print("Not Possible")
else:
print(getMin(a,k))
Producción
9
Complejidad de tiempo: O(N * log(MAX)) donde N es el número total de elementos en la array y MAX es el elemento máximo en la array.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por joshi_arihant y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA