Dadas dos arrays, caja[] y camión[], donde caja[i] representa el peso de la i -ésima caja y camión[i] representa la carga máxima que puede transportar el i -ésimo camión. Ahora cada camión tarda 1 hora en transportar una caja de origen a destino y otra hora en regresar . Ahora, dado que todas las cajas se guardan en el origen, la tarea es encontrar el tiempo mínimo necesario para transportar todas las cajas desde el origen hasta el destino.
Tenga en cuenta que siempre habrá algún momento en el que las cajas se puedan transportar y solo se puede transportar una sola caja por camión en cualquier momento.
Ejemplos:
Entrada: caja[] = {7, 6, 5, 4, 3}, camión[] = {10, 3}
Salida: 7
1.ª hora: camión[0] lleva caja[0] y camión[1] lleva caja[ 4]
2ª hora: Ambos camiones están de regreso en la ubicación de origen.
Ahora, el camión[1] no puede transportar más cajas ya que todas las cajas restantes
tienen pesos superiores a la capacidad de un camión[1].
Entonces, el camión[0] transportará la caja[1] y la caja[2]
en un total de cuatro horas. (origen-destino y luego destino-origen)
Y finalmente, el cuadro[3] tardará otra hora en llegar al destino.
Entonces, tiempo total empleado = 2 + 4 + 1 = 7Entrada: caja[] = {10, 2, 16, 19}, camión[] = {29, 25}
Salida: 3
Enfoque: La idea es utilizar la búsqueda binaria y ordenar las dos arrays. Aquí el límite inferior será 0 y el límite superior será 2 * size of box[] porque, en el peor de los casos, la cantidad de tiempo necesario para transportar todas las cajas será 2 * size of box array. Ahora calcule el valor medio y, para cada valor medio, compruebe si los cargadores pueden transportar todas las cajas en el tiempo = medio. En caso afirmativo, actualice el límite superior como mid – 1 y, si no, actualice el límite inferior como mid + 1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function that returns true if it is
// possible to transport all the boxes
// in the given amount of time
bool isPossible(int box[], int truck[],
int n, int m, int min_time)
{
int temp = 0;
int count = 0;
while (count < m) {
for (int j = 0; j < min_time
&& temp < n
&& truck[count] >= box[temp];
j += 2)
temp++;
count++;
}
// If all the boxes can be
// transported in the given time
if (temp == n)
return true;
// If all the boxes can't be
// transported in the given time
return false;
}
// Function to return the minimum time required
int minTime(int box[], int truck[], int n, int m)
{
// Sort the two arrays
sort(box, box + n);
sort(truck, truck + m);
int l = 0;
int h = 2 * n;
// Stores minimum time in which
// all the boxes can be transported
int min_time = 0;
// Check for the minimum time in which
// all the boxes can be transported
while (l <= h) {
int mid = (l + h) / 2;
// If it is possible to transport all
// the boxes in mid amount of time
if (isPossible(box, truck, n, m, mid)) {
min_time = mid;
h = mid - 1;
}
else
l = mid + 1;
}
return min_time;
}
// Driver code
int main()
{
int box[] = { 10, 2, 16, 19 };
int truck[] = { 29, 25 };
int n = sizeof(box) / sizeof(int);
int m = sizeof(truck) / sizeof(int);
printf("%d", minTime(box, truck, n, m));
return 0;
}
Java
// Java implementation of the approach
import java.util.Arrays;
class GFG
{
// Function that returns true if it is
// possible to transport all the boxes
// in the given amount of time
static boolean isPossible(int box[], int truck[],
int n, int m, int min_time)
{
int temp = 0;
int count = 0;
while (count < m)
{
for (int j = 0; j < min_time
&& temp < n
&& truck[count] >= box[temp];
j += 2)
temp++;
count++;
}
// If all the boxes can be
// transported in the given time
if (temp == n)
return true;
// If all the boxes can't be
// transported in the given time
return false;
}
// Function to return the minimum time required
static int minTime(int box[], int truck[], int n, int m)
{
// Sort the two arrays
Arrays.sort(box);
Arrays.sort(truck);
int l = 0;
int h = 2 * n;
// Stores minimum time in which
// all the boxes can be transported
int min_time = 0;
// Check for the minimum time in which
// all the boxes can be transported
while (l <= h) {
int mid = (l + h) / 2;
// If it is possible to transport all
// the boxes in mid amount of time
if (isPossible(box, truck, n, m, mid))
{
min_time = mid;
h = mid - 1;
}
else
l = mid + 1;
}
return min_time;
}
// Driver code
public static void main(String[] args)
{
int box[] = { 10, 2, 16, 19 };
int truck[] = { 29, 25 };
int n = box.length;
int m = truck.length;
System.out.printf("%d", minTime(box, truck, n, m));
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python3 implementation of the approach # Function that returns true if it is # possible to transport all the boxes # in the given amount of time def isPossible(box, truck, n, m, min_time) : temp = 0 count = 0 while (count < m) : j = 0 while (j < min_time and temp < n and truck[count] >= box[temp] ): temp +=1 j += 2 count += 1 # If all the boxes can be # transported in the given time if (temp == n) : return True # If all the boxes can't be # transported in the given time return False # Function to return the minimum time required def minTime(box, truck, n, m) : # Sort the two arrays box.sort(); truck.sort(); l = 0 h = 2 * n # Stores minimum time in which # all the boxes can be transported min_time = 0 # Check for the minimum time in which # all the boxes can be transported while (l <= h) : mid = (l + h) // 2 # If it is possible to transport all # the boxes in mid amount of time if (isPossible(box, truck, n, m, mid)) : min_time = mid h = mid - 1 else : l = mid + 1 return min_time # Driver code if __name__ == "__main__" : box = [ 10, 2, 16, 19 ] truck = [ 29, 25 ] n = len(box) m = len(truck) print(minTime(box, truck, n, m)) # This code is contributed by Ryuga
C#
// C# implementation of the approach
using System;
class GFG
{
// Function that returns true if it is
// possible to transport all the boxes
// in the given amount of time
static bool isPossible(int []box, int []truck,
int n, int m, int min_time)
{
int temp = 0;
int count = 0;
while (count < m)
{
for (int j = 0; j < min_time
&& temp < n
&& truck[count] >= box[temp];
j += 2)
temp++;
count++;
}
// If all the boxes can be
// transported in the given time
if (temp == n)
return true;
// If all the boxes can't be
// transported in the given time
return false;
}
// Function to return the minimum time required
static int minTime(int []box, int []truck, int n, int m)
{
// Sort the two arrays
Array.Sort(box);
Array.Sort(truck);
int l = 0;
int h = 2 * n;
// Stores minimum time in which
// all the boxes can be transported
int min_time = 0;
// Check for the minimum time in which
// all the boxes can be transported
while (l <= h)
{
int mid = (l + h) / 2;
// If it is possible to transport all
// the boxes in mid amount of time
if (isPossible(box, truck, n, m, mid))
{
min_time = mid;
h = mid - 1;
}
else
l = mid + 1;
}
return min_time;
}
// Driver code
public static void Main(String[] args)
{
int[] box = { 10, 2, 16, 19 };
int []truck = { 29, 25 };
int n = box.Length;
int m = truck.Length;
Console.WriteLine("{0}", minTime(box, truck, n, m));
}
}
/* This code contributed by PrinciRaj1992 */
PHP
<?php
// PHP implementation of the approach
// Function that returns true if it is
// possible to transport all the boxes
// in the given amount of time
function isPossible($box, $truck,
$n, $m, $min_time)
{
$temp = 0;
$count = 0;
while ($count < $m)
{
for ( $j = 0; $j < $min_time
&& $temp < $n
&& $truck[$count] >= $box[$temp];
$j += 2)
$temp++;
$count++;
}
// If all the boxes can be
// transported in the given time
if ($temp == $n)
return true;
// If all the boxes can't be
// transported in the given time
return false;
}
// Function to return the minimum time required
function minTime( $box, $truck, $n, $m)
{
// Sort the two arrays
sort($box);
sort($truck);
$l = 0;
$h = 2 * $n;
// Stores minimum time in which
// all the boxes can be transported
$min_time = 0;
// Check for the minimum time in which
// all the boxes can be transported
while ($l <= $h) {
$mid = intdiv(($l + $h) , 2);
// If it is possible to transport all
// the boxes in mid amount of time
if (isPossible($box, $truck, $n, $m, $mid))
{
$min_time = $mid;
$h = $mid - 1;
}
else
$l = $mid + 1;
}
return $min_time;
}
// Driver code
$box = array( 10, 2, 16, 19 );
$truck = array( 29, 25 );
$n = sizeof($box);
$m = sizeof($truck);
echo minTime($box, $truck, $n, $m);
// This code is contributed by ihritik
?>
Javascript
<script>
// Js implementation of the approach
// Function that returns true if it is
// possible to transport all the boxes
// in the given amount of time
function isPossible( box, truck,
n, m, min_time)
{
let temp = 0;
let count = 0;
while (count < m) {
for (let j = 0; j < min_time
&& temp < n
&& truck[count] >= box[temp];
j += 2)
temp++;
count++;
}
// If all the boxes can be
// transported in the given time
if (temp == n)
return true;
// If all the boxes can't be
// transported in the given time
return false;
}
// Function to return the minimum time required
function minTime(box, truck, n, m)
{
// Sort the two arrays
box.sort(function(a,b){return a-b });
truck.sort(function(a,b){return a-b });
let l = 0;
let h = 2 * n;
// Stores minimum time in which
// all the boxes can be transported
let min_time = 0;
// Check for the minimum time in which
// all the boxes can be transported
while (l <= h) {
let mid = Math.floor((l + h) / 2);
// If it is possible to transport all
// the boxes in mid amount of time
if (isPossible(box, truck, n, m, mid)) {
min_time = mid;
h = mid - 1;
}
else
l = mid + 1;
}
return min_time;
}
// Driver code
let box = [ 10, 2, 16, 19 ];
let truck = [ 29, 25 ];
let n = box.length;
let m = truck.length;
document.write(minTime(box, truck, n, m));
</script>
3
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Sakshi_Srivastava y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA