Минимальное время, необходимое для транспортировки всех ящиков от источника до места назначения при заданных ограничениях
Даны два массива: box [] и truck [], где box [i] представляет вес i- го контейнера, а truck [i] представляет максимальную нагрузку, которую может нести i- й грузовик. Теперь каждому грузовику требуется 1 час, чтобы перевезти коробку из пункта отправления в пункт назначения, и еще один час, чтобы вернуться обратно . Теперь, учитывая, что все ящики хранятся у источника, задача состоит в том, чтобы найти минимальное время, необходимое для транспортировки всех ящиков от источника к месту назначения.
Обратите внимание, что всегда будет какое-то время, в течение которого коробки можно будет транспортировать, и только один ящик может быть перевезен грузовиком в любой момент времени.
Примеры:
Input: box[] = {7, 6, 5, 4, 3}, truck[] = {10, 3}
Output: 7
1st hour: truck[0] carries box[0] and truck[1] carries box[4]
2nd hour: Both trucks are back at the source location.
Now, truck[1] cannot carry anymore boxes as all the remaining boxes
have weights more than the capacity of a truck[1].
So, truck[0] will carry box[1] and box[2]
in a total of four hours. (source-destination and then destination-source)
And finally, box[3] will take another hour to reach the destination.
So, total time taken = 2 + 4 + 1 = 7Input: box[] = {10, 2, 16, 19}, truck[] = {29, 25}
Output: 3
Подход: идея состоит в том, чтобы использовать двоичный поиск и отсортировать два массива. Здесь нижняя граница будет равна 0, а верхняя граница будет 2 * размер box [], потому что в худшем случае количество времени, необходимое для транспортировки всех ящиков, будет 2 * размера массива ящиков. Теперь вычислите среднее значение и для каждого среднего значения проверьте, все ли коробки могут быть перевезены загрузчиками за time = mid. Если да, то обновите верхнюю границу как mid - 1, а если нет, то обновите нижнюю границу как mid + 1 .
Below is the implementation of the above approach:
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 timebool 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 requiredint 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 codeint 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 approachimport java.util.Arrays;class GFG{// Function that returns true if it is// possible to transport all the boxes// in the given amount of timestatic 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 requiredstatic 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 codepublic 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 timedef 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 requireddef 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 codeif __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 approachusing System; class GFG{// Function that returns true if it is// possible to transport all the boxes// in the given amount of timestatic 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 requiredstatic 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 codepublic 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 timefunction 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 requiredfunction 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РЕКОМЕНДУЕМЫЕ СТАТЬИ |