Dada una array ordenada ascendente arr[] de tamaño N y un número entero K , la tarea es dividir la array dada en K subarreglos no vacíos de modo que la suma de las diferencias del máximo y el mínimo de cada subarreglo se minimice.
Ejemplos:
Entrada: arr[] = { 10, 20, 70, 80 }, N = 4, K = 2
Salida: 20
Explicación: La array dada se puede dividir de la siguiente manera
{10, 20} y {70, 80}. Las diferencias son (20 – 10) = 10 y (80 – 70) = 10
La suma = 10 + 10 = 20Entrada: arr[] = { 5, 10, 50, 70 }, N = 4, K = 3
Salida: 5
Explicación: Los subarreglos son {5, 10}, {50}, {70}
Las diferencias son 10 – 5 = 5, 50 – 50 = 0, 70 – 70 = 0
La suma = 5 + 0 + 0 = 5
Enfoque: Los otros enfoques se analizan en el Conjunto 1 de este artículo . Aquí, estamos discutiendo el enfoque de búsqueda binaria.
Enfoque de espacio optimizado: la idea es utilizar la búsqueda binaria para encontrar la respuesta. La respuesta está en [ 0, ( arr[N-1] – arr[0]) ]. Ver la siguiente observación para la justificación.
- Suponiendo permiso para hacer tantos cortes como sea posible, la respuesta sería 0 porque cada elemento puede formar un subarreglo. Por lo tanto, el valor mínimo sería 0 .
- Ahora, el otro caso extremo puede ser cuando solo se permite un subarreglo. En este caso, la respuesta sería (arr[N-1] – arr[0]) . Estos eran los dos casos extremos y se garantiza que la respuesta estaría entre ellos.
Siga los pasos a continuación para resolver el problema:
- Inicialice la variable ans como 0 para almacenar la respuesta.
- Aplique la búsqueda binaria con low = 0 y high = arr[N-1] – arr[0] .
- Para cada valor de mid , verifique si una cinta de longitud mid puede cubrir todos los agujeros dentro de los cortes K.
- Si es así, hemos llegado a una posible respuesta. Guarde el valor y verifique si es posible hacer lo mismo para una cinta de menor longitud. (hacer alto = medio – 1 )
- De lo contrario, encuentre un valor mayor para mid ( low = mid + 1 ).
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;
bool isValid(vector<int> arr, int max_cuts, int len)
{
// Max_cuts is the maximum no. of
// allowed cuts.
int n = arr.size();
int start = 0;
int i = 1;
while (i < n) {
// Start from covering as many holes
// as you can from start.
if (arr[i] - arr[start] <= len) {
i++;
}
else {
// If an index is reached
// from where it's not possible
// to accommodate more elements
// in the current subarray
// then end this subarray
// and go further.
len = len - (arr[i - 1] - arr[start]);
max_cuts--;
start = i;
i++;
}
// If at any point you run out
// of maximum subarrays or length
// then return false because it's
// impossible to obtain this
// value of mid.
if (max_cuts <= 0 || len <= 0)
return false;
}
// Covered all subarrays within
// the sum maximum number of subarrays
// so return true.
return true;
}
// Function to find the minimum sum
void findMinTapeLength(vector<int> arr, int N, int K)
{
// Initialise low and high
int high = arr[N - 1] - arr[0], low = 0;
int ans = 0;
// Apply Binary Search
while (low <= high) {
int mid = low + (high - low) / 2;
// IsValid() function checks if
// max value of mid is sufficient
// to break the array in K subarrays
if (isValid(arr, K, mid)) {
// If true then set this as
// the current answer and divide
// your range to [low, mid-1]
// to check for a lower sum
ans = mid;
high = mid - 1;
}
// If false then that means need
// to increase the current length
// so set range to [mid+1, high]
else
low = mid + 1;
}
cout << ans;
}
// Driver Code
int main()
{
vector<int> arr = { 10, 20, 70, 80 };
int N = 4, K = 2;
findMinTapeLength(arr, N, K);
}
// This code is contributed by Samim Hossain Mondal.
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to find the minimum sum
static void findMinTapeLength(int[] arr,
int N, int K)
{
// Initialise low and high
int high = arr[N - 1] - arr[0], low = 0;
int ans = 0;
// Apply Binary Search
while (low <= high) {
int mid = low + (high - low) / 2;
// IsValid() function checks if
// max value of mid is sufficient
// to break the array in K subarrays
if (isValid(arr, K, mid)) {
// If true then set this as
// the current answer and divide
// your range to [low, mid-1]
// to check for a lower sum
ans = mid;
high = mid - 1;
}
// If false then that means need
// to increase the current length
// so set range to [mid+1, high]
else
low = mid + 1;
}
System.out.println(ans);
}
static boolean isValid(int[] arr,
int max_cuts,
int len)
{
// Max_cuts is the maximum no. of
// allowed cuts.
int n = arr.length;
int start = 0;
int i = 1;
while (i < n) {
// Start from covering as many holes
// as you can from start.
if (arr[i] - arr[start] <=
len) {
i++;
}
else {
// If an index is reached
// from where it's not possible
// to accommodate more elements
// in the current subarray
// then end this subarray
// and go further.
len = len - (arr[i - 1] -
arr[start]);
max_cuts--;
start = i;
i++;
}
// If at any point you run out
// of maximum subarrays or length
// then return false because it's
// impossible to obtain this
// value of mid.
if (max_cuts <= 0 || len <= 0)
return false;
}
// Covered all subarrays within
// the sum maximum number of subarrays
// so return true.
return true;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 10, 20, 70, 80 };
int N = 4, K = 2;
findMinTapeLength(arr, N, K);
}
}
Python3
# Python code for the above approach # Function to find the minimum sum def findMinTapeLength(arr, N, K): # Initialise low and high high = arr[N - 1] - arr[0] low = 0 ans = 0 # Apply Binary Search while (low <= high): mid = low + ((high - low) // 2) # IsValid() function checks if # max value of mid is sufficient # to break the array in K subarrays if (isValid(arr, K, mid)): # If true then set this as # the current answer and divide # your range to [low, mid-1] # to check for a lower sum ans = mid high = mid - 1 # If false then that means need # to increase the current length # so set range to [mid+1, high] else: low = mid + 1 print(ans) def isValid(arr, max_cuts, _len): # Max_cuts is the maximum no. of # allowed cuts. n = len(arr) start = 0 i = 1 while (i < n): # Start from covering as many holes # as you can from start. if (arr[i] - arr[start] <= _len): i += 1 else: # If an index is reached # from where it's not possible # to accommodate more elements # in the current subarray # then end this subarray # and go further. _len = _len - (arr[i - 1] - arr[start]) max_cuts -= 1 start = i i += 1 # If at any point you run out # of maximum subarrays or length # then return false because it's # impossible to obtain this # value of mid. if (max_cuts <= 0 or _len <= 0): return False # Covered all subarrays within # the sum maximum number of subarrays # so return true. return True # Driver Code arr = [10, 20, 70, 80] N = 4 K = 2 findMinTapeLength(arr, N, K) # This code is contributed by gfgking
C#
// C# program for the above approach
using System;
class GFG {
// Function to find the minimum sum
static void findMinTapeLength(int[] arr,
int N, int K)
{
// Initialise low and high
int high = arr[N - 1] - arr[0], low = 0;
int ans = 0;
// Apply Binary Search
while (low <= high) {
int mid = low + (high - low) / 2;
// IsValid() function checks if
// max value of mid is sufficient
// to break the array in K subarrays
if (isValid(arr, K, mid)) {
// If true then set this as
// the current answer and divide
// your range to [low, mid-1]
// to check for a lower sum
ans = mid;
high = mid - 1;
}
// If false then that means need
// to increase the current length
// so set range to [mid+1, high]
else
low = mid + 1;
}
Console.WriteLine(ans);
}
static bool isValid(int[] arr,
int max_cuts,
int len)
{
// Max_cuts is the maximum no. of
// allowed cuts.
int n = arr.Length;
int start = 0;
int i = 1;
while (i < n) {
// Start from covering as many holes
// as you can from start.
if (arr[i] - arr[start] <=
len) {
i++;
}
else {
// If an index is reached
// from where it's not possible
// to accommodate more elements
// in the current subarray
// then end this subarray
// and go further.
len = len - (arr[i - 1] -
arr[start]);
max_cuts--;
start = i;
i++;
}
// If at any point you run out
// of maximum subarrays or length
// then return false because it's
// impossible to obtain this
// value of mid.
if (max_cuts <= 0 || len <= 0)
return false;
}
// Covered all subarrays within
// the sum maximum number of subarrays
// so return true.
return true;
}
// Driver Code
public static void Main()
{
int[] arr = { 10, 20, 70, 80 };
int N = 4, K = 2;
findMinTapeLength(arr, N, K);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to find the minimum sum
function findMinTapeLength(arr,
N, K)
{
// Initialise low and high
let high = arr[N - 1] - arr[0], low = 0;
let ans = 0;
// Apply Binary Search
while (low <= high)
{
let mid = low + Math.floor((high - low) / 2);
// IsValid() function checks if
// max value of mid is sufficient
// to break the array in K subarrays
if (isValid(arr, K, mid)) {
// If true then set this as
// the current answer and divide
// your range to [low, mid-1]
// to check for a lower sum
ans = mid;
high = mid - 1;
}
// If false then that means need
// to increase the current length
// so set range to [mid+1, high]
else
low = mid + 1;
}
document.write(ans);
}
function isValid(arr, max_cuts, len)
{
// Max_cuts is the maximum no. of
// allowed cuts.
let n = arr.length;
let start = 0;
let i = 1;
while (i < n) {
// Start from covering as many holes
// as you can from start.
if (arr[i] - arr[start] <=
len) {
i++;
}
else {
// If an index is reached
// from where it's not possible
// to accommodate more elements
// in the current subarray
// then end this subarray
// and go further.
len = len - (arr[i - 1] -
arr[start]);
max_cuts--;
start = i;
i++;
}
// If at any point you run out
// of maximum subarrays or length
// then return false because it's
// impossible to obtain this
// value of mid.
if (max_cuts <= 0 || len <= 0)
return false;
}
// Covered all subarrays within
// the sum maximum number of subarrays
// so return true.
return true;
}
// Driver Code
let arr = [10, 20, 70, 80];
let N = 4, K = 2;
findMinTapeLength(arr, N, K);
// This code is contributed by Potta Lokesh
</script>
Producción
20
Complejidad de tiempo: O(N*log(M)), donde M es el valor máximo de la array.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por amrithabpatil y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA