Dada una array arr[] que consta de las alturas de N barras de chocolate, la tarea es encontrar la altura máxima a la que se realiza el corte horizontal a todos los chocolates de modo que la suma de la cantidad restante de chocolate sea al menos K .
Ejemplos:
Entrada: K = 7, arr[] = [15, 20, 8, 17]
Salida: 15
Explicación:
Supongamos que se hace un corte a la altura 8:
-> chocolate tomado de la 1ra barra de chocolate = 15 – 8 =7
-> chocolate extraído de la 2.ª barra de chocolate = 20 – 8 = 12
-> chocolate extraído de la 3.ª barra de chocolate = 8 – 8 = 0
-> chocolate extraído de la 4.ª barra de chocolate = 17 – 8 = 9
=> Chocolate total desperdiciado = (7 + 12 + 0 + 9) – K = 28 – 7 = 21Supongamos que se hace un corte a la altura 15:
-> chocolate extraído de la 1ª barra de chocolate = 15 – 15 = 0
-> chocolate extraído de la 2ª barra de chocolate = 20 – 15 = 5
-> no se elegirá la 3ª barra de chocolate porque es menor que 15
-> chocolate tomado de la 4ta barra de chocolate = 17 – 15 = 2
=> Total de chocolate desperdiciado = (0 + 5 + 2) – K = 7 – 7 = 0Por lo tanto, cuando tomamos chocolate de altura 15, el desperdicio de chocolate es mínimo. Por lo tanto, 15 es la respuesta.
Entrada: K = 12, arr[] = [30, 25, 22, 17, 20]
Salida: 21
Explicación:
Después de un corte a la altura 18, el chocolate eliminado es 25 y el desperdicio de chocolate es (25 – 12) = 13 unidades. Pero si el corte se hace a la altura 21 entonces se sacan 14 unidades de chocolate y el desperdicio es (14 – 12) = 2 que es lo mínimo, por lo tanto 21 es la respuesta
Enfoque: el problema dado se puede resolver en función de la búsqueda binaria .
La idea es realizar la búsqueda binaria en el rango [0, elemento máximo de la array ] y encontrar ese valor en el rango, digamos M, de modo que la suma del chocolate restante después de hacer el corte horizontal en M dé una diferencia mínima con K .
Siga los pasos a continuación para resolver el problema dado:
- Inicialice dos variables, digamos low y high como 0 y el elemento de array máximo respectivamente.
- Iterar hasta bajo <= alto y realizar los siguientes pasos:
- Encuentre el valor de mid como (low + high)/2 .
- Encuentre la suma de los chocolates restantes después de hacer el corte horizontal a la altura de la mitad de M .
- Si el valor de M es menor que K , actualice el valor de alto como (medio – 1) . De lo contrario, actualice el valor de low como (mid + 1) .
- Después de realizar los pasos anteriores, imprima el valor tan alto como la altura máxima resultante que se debe cortar.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the sum of remaining
// chocolate after making the horizontal
// cut at height mid
int cal(vector<int> arr, int mid)
{
// Stores the sum of chocolates
int chocolate = 0;
// Traverse the array arr[]
for (auto i : arr) {
// If the height is at least mid
if (i >= mid)
chocolate += i - mid;
}
// Return the possible sum
return chocolate;
}
// Function to find the maximum horizontal
// cut made to all the chocolates such that
// the sum of the remaining element is
// at least K
int maximumCut(vector<int> arr, int K)
{
// Ranges of Binary Search
int low = 0;
int high = *max_element(arr.begin(), arr.end());
// Perform the Binary Search
while (low <= high) {
int mid = (low + high) / 2;
// Find the sum of removed after
// making cut at height mid
int chocolate = cal(arr, mid);
// If the chocolate removed is
// same as the chocolate needed
// then return the height
if (chocolate == K)
return mid;
// If the chocolate removed is
// less than chocolate needed
// then shift to the left range
else if (chocolate < K)
high = mid - 1;
// Otherwise, shift to the right
// range
else {
low = mid + 1;
if (mid > high)
high = mid;
}
}
// Return the possible cut
return high;
}
// Driver Code
int main()
{
int N = 4;
int K = 7;
vector<int> arr{ 15, 20, 8, 17 };
cout << (maximumCut(arr, K));
}
// This code is contributed by ipg2016107.
Java
// Java program for the above approach
import java.util.*;
import java.util.Arrays;
class GFG {
// Function to find the sum of remaining
// chocolate after making the horizontal
// cut at height mid
static int cal(int arr[], int mid)
{
// Stores the sum of chocolates
int chocolate = 0;
// Traverse the array arr[]
for (int i = 0; i < arr.length; i++) {
// If the height is at least mid
if (arr[i] >= mid)
chocolate += arr[i] - mid;
}
// Return the possible sum
return chocolate;
}
// Function to find the maximum horizontal
// cut made to all the chocolates such that
// the sum of the remaining element is
// at least K
static int maximumCut(int arr[], int K)
{
// Ranges of Binary Search
int low = 0;
int high = Arrays.stream(arr).max().getAsInt();
// Perform the Binary Search
while (low <= high) {
int mid = (low + high) / 2;
// Find the sum of removed after
// making cut at height mid
int chocolate = cal(arr, mid);
// If the chocolate removed is
// same as the chocolate needed
// then return the height
if (chocolate == K)
return mid;
// If the chocolate removed is
// less than chocolate needed
// then shift to the left range
else if (chocolate < K)
high = mid - 1;
// Otherwise, shift to the right
// range
else {
low = mid + 1;
if (mid > high)
high = mid;
}
}
// Return the possible cut
return high;
}
// Driver Code
public static void main(String[] args)
{
int K = 7;
int arr[] = { 15, 20, 8, 17 };
System.out.println(maximumCut(arr, K));
}
}
// This code is contributed by ukasp.
Python3
# Python program for the above approach # Function to find the sum of remaining # chocolate after making the horizontal # cut at height mid def cal(arr, mid): # Stores the sum of chocolates chocolate = 0 # Traverse the array arr[] for i in arr: # If the height is at least mid if i >= mid: chocolate += i - mid # Return the possible sum return chocolate # Function to find the maximum horizontal # cut made to all the chocolates such that # the sum of the remaining element is # at least K def maximumCut(arr, K): # Ranges of Binary Search low = 0 high = max(arr) # Perform the Binary Search while low <= high: mid = (low + high) // 2 # Find the sum of removed after # making cut at height mid chocolate = cal(arr, mid) # If the chocolate removed is # same as the chocolate needed # then return the height if chocolate == K: return mid # If the chocolate removed is # less than chocolate needed # then shift to the left range elif chocolate < K: high = mid - 1 # Otherwise, shift to the right # range else: low = mid + 1 if mid > high: high = mid # Return the possible cut return high # Driver Code N, K = 4, 7 arr = [15, 20, 8, 17] print(maximumCut(arr, K))
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
class GFG {
// Function to find the sum of remaining
// chocolate after making the horizontal
// cut at height mid
static int cal(List<int> arr, int mid)
{
// Stores the sum of chocolates
int chocolate = 0;
// Traverse the array arr[]
foreach(int i in arr)
{
// If the height is at least mid
if (i >= mid)
chocolate += i - mid;
}
// Return the possible sum
return chocolate;
}
// Function to find the maximum horizontal
// cut made to all the chocolates such that
// the sum of the remaining element is
// at least K
static int maximumCut(List<int> arr, int K)
{
// Ranges of Binary Search
int low = 0;
int high = arr.Max();
// Perform the Binary Search
while (low <= high) {
int mid = (low + high) / 2;
// Find the sum of removed after
// making cut at height mid
int chocolate = cal(arr, mid);
// If the chocolate removed is
// same as the chocolate needed
// then return the height
if (chocolate == K)
return mid;
// If the chocolate removed is
// less than chocolate needed
// then shift to the left range
else if (chocolate < K)
high = mid - 1;
// Otherwise, shift to the right
// range
else {
low = mid + 1;
if (mid > high)
high = mid;
}
}
// Return the possible cut
return high;
}
// Driver Code
public static void Main()
{
int K = 7;
List<int> arr = new List<int>() { 15, 20, 8, 17 };
Console.Write(maximumCut(arr, K));
}
}
// This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the sum of remaining
// chocolate after making the horizontal
// cut at height mid
function cal(arr, mid) {
// Stores the sum of chocolates
let chocolate = 0
// Traverse the array arr[]
for (let i = 0; i < arr.length; i++) {
// If the height is at least mid
if (arr[i] >= mid)
chocolate += arr[i] - mid
}
// Return the possible sum
return chocolate
}
// Function to find the maximum horizontal
// cut made to all the chocolates such that
// the sum of the remaining element is
// at least K
function maximumCut(arr, K) {
// Ranges of Binary Search
let low = 0
let high = arr[0];
for (let i = 1; i < arr.length; i++) {
high = Math.max(high, arr[i]);
}
// Perform the Binary Search
while (low <= high) {
mid = Math.floor((low + high) / 2);
// Find the sum of removed after
// making cut at height mid
chocolate = cal(arr, mid)
// If the chocolate removed is
// same as the chocolate needed
// then return the height
if (chocolate == K) {
return mid
}
// If the chocolate removed is
// less than chocolate needed
// then shift to the left range
else if (chocolate < K) {
high = mid - 1
}
// Otherwise, shift to the right
// range
else {
low = mid + 1
if (mid > high)
high = mid
}
}
// Return the possible cut
return high
}
// Driver Code
let N = 4;
let K = 7;
let arr = [15, 20, 8, 17];
document.write(maximumCut(arr, K))
// This code is contributed by Potta Lokesh
</script>
15
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)