Dadas N varillas de diferentes longitudes. La tarea es cortar todas las varillas con alguna altura entera máxima ‘h’ tal que la suma de las longitudes de corte de la varilla se maximice y debe ser mayor que M. Imprima -1 si no es posible tal corte.
Nota: Una varilla no se puede cortar también.
Ejemplos:
Entrada: N = 7, M = 8, a[] = {1, 2, 3, 5, 4, 7, 6}
Salida: 3 Las
varillas 1 y 2 no se tocan, y las varillas 3, 4, 5, 6, 7 se cortan con las longitudes de corte que son (3-3) + (4-3) + (5-3) + (7-3) + (6-3) que es igual a 10 que es mayor que M = 8
Entrada: N = 4, M = 2, a[] = {1, 2, 3, 3}
Salida: 2
Acercarse:
- Ordenar la array en orden ascendente
- Ejecute una búsqueda binaria con valores bajo=0 y alto=longitud[n-1], tal que medio=(bajo+alto)/2.
- Ejecute un ciclo desde n-1 hasta 0 agregando la altura del corte de la varilla a la suma.
- Si la suma es mayor o igual a m, asigne low con mid+1; de lo contrario, high se actualizará con mid.
- Después de completar la búsqueda binaria, la respuesta será baja-1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the maximum possible
// length of rod which will be cut such that
// sum of cut off lengths will be maximum
#include <bits/stdc++.h>
using namespace std;
// Function to run Binary Search to
// find maximum cut off length
int binarySearch(int adj[], int target, int length)
{
int low = 0;
int high = adj[length - 1];
while (low < high) {
// f is the flag variable
// sum is for the total length cutoff
int f = 0, sum = 0;
int mid = low + (high - low) / 2;
// Loop from higher to lower
// for optimization
for (int i = length - 1; i >= 0; i--) {
// Only if length is greater
// than cut-off length
if (adj[i] > mid) {
sum = sum + adj[i] - mid;
}
// When total cut off length becomes greater
// than desired cut off length
if (sum >= target) {
f = 1;
low = mid + 1;
break;
}
}
// If flag variable is not set
// Change high
if (f == 0)
high = mid;
}
// returning the maximum cut off length
return low - 1;
}
// Driver Function
int main()
{
int n1 = 7;
int n2 = 8;
int adj[] = { 1, 2, 3, 4, 5, 7, 6 };
// Sorting the array in ascending order
sort(adj, adj + n1);
// Calling the binarySearch Function
cout << binarySearch(adj, n2, n1);
}
Java
// Java program to find the
// maximum possible length
// of rod which will be cut
// such that sum of cut off
// lengths will be maximum
import java.util.*;
class GFG
{
// Function to run Binary
// Search to find maximum
// cut off length
static int binarySearch(int adj[],
int target,
int length)
{
int low = 0;
int high = adj[length - 1];
while (low < high)
{
// f is the flag variable
// sum is for the total
// length cutoff
int f = 0, sum = 0;
int mid = low + (high - low) / 2;
// Loop from higher to lower
// for optimization
for (int i = length - 1;
i >= 0; i--)
{
// Only if length is greater
// than cut-off length
if (adj[i] > mid)
{
sum = sum + adj[i] - mid;
}
// When total cut off length
// becomes greater than
// desired cut off length
if (sum >= target)
{
f = 1;
low = mid + 1;
break;
}
}
// If flag variable is
// not set Change high
if (f == 0)
high = mid;
}
// returning the maximum
// cut off length
return low - 1;
}
// Driver Code
public static void main(String args[])
{
int n1 = 7;
int n2 = 8;
int adj[] = { 1, 2, 3, 4, 5, 7, 6 };
// Sorting the array
// in ascending order
Arrays.sort(adj);
// Calling the binarySearch Function
System.out.println(binarySearch(adj, n2, n1));
}
}
// This code is contributed
// by Arnab Kundu
Python3
# Python 3 program to find the # maximum possible length of # rod which will be cut such # that sum of cut off lengths # will be maximum # Function to run Binary Search # to find maximum cut off length def binarySearch(adj, target, length) : low = 0 high = adj[length - 1] while (low < high) : # f is the flag variable # sum is for the total # length cutoff # multiple assignments f, sum = 0, 0 # take integer value mid = low + (high - low) // 2; # Loop from higher to lower # for optimization for i in range(length - 1, -1 , -1) : # Only if length is greater # than cut-off length if adj[i] > mid : sum = sum + adj[i] - mid # When total cut off length # becomes greater than # desired cut off length if sum >= target : f = 1 low = mid + 1 break # If flag variable is # not set. Change high if f == 0 : high = mid # returning the maximum # cut off length return low - 1 # Driver code if __name__ == "__main__" : n1 = 7 n2 = 8 # adj = [1,2,3,3] adj = [ 1, 2, 3, 4, 5, 7, 6] # Sorting the array # in ascending order adj.sort() # Calling the binarySearch Function print(binarySearch(adj, n2, n1)) # This code is contributed # by ANKITRAI1
C#
// C# program to find the
// maximum possible length
// of rod which will be cut
// such that sum of cut off
// lengths will be maximum
using System;
class GFG
{
// Function to run Binary
// Search to find maximum
// cut off length
static int binarySearch(int []adj,
int target,
int length)
{
int low = 0;
int high = adj[length - 1];
while (low < high)
{
// f is the flag variable
// sum is for the total
// length cutoff
int f = 0, sum = 0;
int mid = low + (high - low) / 2;
// Loop from higher to lower
// for optimization
for (int i = length - 1;
i >= 0; i--)
{
// Only if length is greater
// than cut-off length
if (adj[i] > mid)
{
sum = sum + adj[i] - mid;
}
// When total cut off length
// becomes greater than
// desired cut off length
if (sum >= target)
{
f = 1;
low = mid + 1;
break;
}
}
// If flag variable is
// not set Change high
if (f == 0)
high = mid;
}
// returning the maximum
// cut off length
return low - 1;
}
// Driver Code
public static void Main()
{
int n1 = 7;
int n2 = 8;
int []adj = {1, 2, 3, 4, 5, 7, 6};
// Sorting the array
// in ascending order
Array.Sort(adj);
// Calling the binarySearch Function
Console.WriteLine(binarySearch(adj, n2, n1));
}
}
// This code is contributed
// by Subhadeep Gupta
PHP
<?php
// PHP program to find the maximum
// possible length of rod which will
// be cut such that sum of cut off
// lengths will be maximum
// Function to run Binary Search
// to find maximum cut off length
function binarySearch(&$adj, $target,
$length)
{
$low = 0;
$high = $adj[$length - 1];
while ($low < $high)
{
// f is the flag variable
// sum is for the total
// length cutoff
$f = 0;
$sum = 0;
$mid = $low + ($high - $low) / 2;
// Loop from higher to lower
// for optimization
for ($i = $length - 1; $i >= 0; $i--)
{
// Only if length is greater
// than cut-off length
if ($adj[$i] > $mid)
{
$sum = $sum + $adj[$i] - $mid;
}
// When total cut off length becomes
// greater than desired cut off length
if ($sum >= $target)
{
$f = 1;
$low = $mid + 1;
break;
}
}
// If flag variable is not
// set Change high
if ($f == 0)
$high = $mid;
}
// returning the maximum cut off length
return $low - 1;
}
// Driver Code
$n1 = 7;
$n2 = 8;
$adj = array( 1, 2, 3, 4, 5, 7, 6 );
// Sorting the array in ascending order
sort($adj);
// Calling the binarySearch Function
echo (int)binarySearch($adj, $n2, $n1);
// This code is contributed by ChitraNayal
?>
Javascript
<script>
// Javascript program to find the
// maximum possible length
// of rod which will be cut
// such that sum of cut off
// lengths will be maximum
// Function to run Binary
// Search to find maximum
// cut off length
function binarySearch(adj,target,length)
{
let low = 0;
let high = adj[length - 1];
while (low < high)
{
// f is the flag variable
// sum is for the total
// length cutoff
let f = 0, sum = 0;
let mid = low + Math.floor((high - low) / 2);
// Loop from higher to lower
// for optimization
for (let i = length - 1;
i >= 0; i--)
{
// Only if length is greater
// than cut-off length
if (adj[i] > mid)
{
sum = sum + adj[i] - mid;
}
// When total cut off length
// becomes greater than
// desired cut off length
if (sum >= target)
{
f = 1;
low = mid + 1;
break;
}
}
// If flag variable is
// not set Change high
if (f == 0)
high = mid;
}
// returning the maximum
// cut off length
return low - 1;
}
// Driver Code
let n1 = 7;
let n2 = 8;
let adj=[1, 2, 3, 4, 5, 7, 6 ];
// Sorting the array
// in ascending order
adj.sort(function(a,b){return a-b;});
// Calling the binarySearch Function
document.write(binarySearch(adj, n2, n1));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
3
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(1)