Dada una array arr[] que consta de N enteros y un entero D , la tarea es encontrar el menor entero T tal que la array completa se pueda dividir en un máximo de D subarreglos de la array dada con suma como máximo T .
Ejemplos:
Entrada: D = 5, arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Salida: 15
Explicación:
Si T = 15, entonces 5 subarreglos {{1, 2, 3, 4, 5}, {6, 7}, {8}, {9}, {10}}Entrada: D = 2, arr[] = {1, 1, 1, 1, 1}
Salida: 3
Explicación:
Si T = 3, entonces las 2 particiones son {{1, 1, 1}, {1, 1} }
Enfoque ingenuo: la idea es verificar todos los valores posibles de T en el rango [max (elemento), sum (elemento)] si es posible tener como máximo la partición D.
Complejidad temporal: O( N*R )
Espacio auxiliar: O(1)
Enfoque eficiente: la idea es utilizar la búsqueda binaria para optimizar el enfoque anterior. Siga los pasos a continuación para resolver el problema:
- Considere T en el rango R = [ max(elemento), sum(elemento) ] .
- Si la mediana T puede generar como máximo particiones D , busque una mediana menor que T .
- De lo contrario, busque una mediana mayor que la mediana T actual .
- Devuelve el posible valor de T al final.
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 check if the array
// can be partitioned into atmost d
// subarray with sum atmost T
bool possible(int T, int arr[], int n, int d)
{
// Initial partition
int partition = 1;
// Current sum
int total = 0;
for (int i = 0; i < n; i++) {
total = total + arr[i];
// If current sum exceeds T
if (total > T) {
// Create a new partition
partition = partition + 1;
total = arr[i];
// If count of partitions
// exceed d
if (partition > d) {
return false;
}
}
}
return true;
}
// Function to find the minimum
// possible value of T
void calcT(int n, int d, int arr[])
{
// Stores the maximum and
// total sum of elements
int mx = -1, sum = 0;
for (int i = 0; i < n; i++) {
// Maximum element
mx = max(mx, arr[i]);
// Sum of all elements
sum = sum + arr[i];
}
int lb = mx;
int ub = sum;
while (lb < ub) {
// Calculate median T
int T_mid = lb + (ub - lb) / 2;
// If atmost D partitions possible
if (possible(T_mid, arr, n, d) == true) {
// Check for smaller T
ub = T_mid;
}
// Otherwise
else {
// Check for larger T
lb = T_mid + 1;
}
}
// Print the minimum T required
cout << lb << endl;
}
// Driver Code
int main()
{
int d = 2;
int arr[] = { 1, 1, 1, 1, 1 };
int n = sizeof arr / sizeof arr[0];
// Function call
calcT(n, d, arr);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
import java.io.*;
class GFG{
// Function to check if the array
// can be partitioned into atmost d
// subarray with sum atmost T
public static boolean possible(int T, int arr[],
int n, int d)
{
// Initial partition
int partition = 1;
// Current sum
int total = 0;
for(int i = 0; i < n; i++)
{
total = total + arr[i];
// If current sum exceeds T
if (total > T)
{
// Create a new partition
partition = partition + 1;
total = arr[i];
// If count of partitions
// exceed d
if (partition > d)
{
return false;
}
}
}
return true;
}
// Function to find the minimum
// possible value of T
public static void calcT(int n, int d,
int arr[])
{
// Stores the maximum and
// total sum of elements
int mx = -1, sum = 0;
for(int i = 0; i < n; i++)
{
// Maximum element
mx = Math.max(mx, arr[i]);
// Sum of all elements
sum = sum + arr[i];
}
int lb = mx;
int ub = sum;
while (lb < ub)
{
// Calculate median T
int T_mid = lb + (ub - lb) / 2;
// If atmost D partitions possible
if (possible(T_mid, arr, n, d) == true)
{
// Check for smaller T
ub = T_mid;
}
// Otherwise
else
{
// Check for larger T
lb = T_mid + 1;
}
}
// Print the minimum T required
System.out.println(lb);
}
// Driver code
public static void main(String args[])
{
int d = 2;
int arr[] = { 1, 1, 1, 1, 1 };
int n = arr.length;
// Function call
calcT(n, d, arr);
}
}
// This code is contributed by decoding
Python3
# Python3 program for the above approach # Function to check if the array # can be partitioned into atmost d # subarray with sum atmost T def possible(T, arr, n, d): # Initial partition partition = 1; # Current sum total = 0; for i in range(n): total = total + arr[i]; # If current sum exceeds T if (total > T): # Create a new partition partition = partition + 1; total = arr[i]; # If count of partitions # exceed d if (partition > d): return False; return True; # Function to find the minimum # possible value of T def calcT(n, d, arr): # Stores the maximum and # total sum of elements mx = -1; sum = 0; for i in range(n): # Maximum element mx = max(mx, arr[i]); # Sum of all elements sum = sum + arr[i]; lb = mx; ub = sum; while (lb < ub): # Calculate median T T_mid = lb + (ub - lb) // 2; # If atmost D partitions possible if (possible(T_mid, arr, n, d) == True): # Check for smaller T ub = T_mid; # Otherwise else: # Check for larger T lb = T_mid + 1; # Print the minimum T required print(lb); # Driver code if __name__ == '__main__': d = 2; arr = [ 1, 1, 1, 1, 1 ]; n = len(arr); # Function call calcT(n, d, arr); # This code is contributed by Rajput-Ji
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if the array
// can be partitioned into atmost d
// subarray with sum atmost T
public static bool possible(int T, int []arr,
int n, int d)
{
// Initial partition
int partition = 1;
// Current sum
int total = 0;
for(int i = 0; i < n; i++)
{
total = total + arr[i];
// If current sum exceeds T
if (total > T)
{
// Create a new partition
partition = partition + 1;
total = arr[i];
// If count of partitions
// exceed d
if (partition > d)
{
return false;
}
}
}
return true;
}
// Function to find the minimum
// possible value of T
public static void calcT(int n, int d,
int []arr)
{
// Stores the maximum and
// total sum of elements
int mx = -1, sum = 0;
for(int i = 0; i < n; i++)
{
// Maximum element
mx = Math.Max(mx, arr[i]);
// Sum of all elements
sum = sum + arr[i];
}
int lb = mx;
int ub = sum;
while (lb < ub)
{
// Calculate median T
int T_mid = lb + (ub - lb) / 2;
// If atmost D partitions possible
if (possible(T_mid, arr, n, d) == true)
{
// Check for smaller T
ub = T_mid;
}
// Otherwise
else
{
// Check for larger T
lb = T_mid + 1;
}
}
// Print the minimum T required
Console.WriteLine(lb);
}
// Driver code
public static void Main(String []args)
{
int d = 2;
int []arr = { 1, 1, 1, 1, 1 };
int n = arr.Length;
// Function call
calcT(n, d, arr);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for the
// above approach
// Function to check if the array
// can be partitioned into atmost d
// subarray with sum atmost T
function possible(T, arr,
n, d)
{
// Initial partition
let partition = 1;
// Current sum
let total = 0;
for(let i = 0; i < n; i++)
{
total = total + arr[i];
// If current sum exceeds T
if (total > T)
{
// Create a new partition
partition = partition + 1;
total = arr[i];
// If count of partitions
// exceed d
if (partition > d)
{
return false;
}
}
}
return true;
}
// Function to find the minimum
// possible value of T
function calcT(n, d, arr)
{
// Stores the maximum and
// total sum of elements
let mx = -1, sum = 0;
for(let i = 0; i < n; i++)
{
// Maximum element
mx = Math.max(mx, arr[i]);
// Sum of all elements
sum = sum + arr[i];
}
let lb = mx;
let ub = sum;
while (lb < ub)
{
// Calculate median T
let T_mid = lb + (ub - lb) / 2;
// If atmost D partitions possible
if (possible(T_mid, arr, n, d) == true)
{
// Check for smaller T
ub = T_mid;
}
// Otherwise
else
{
// Check for larger T
lb = T_mid + 1;
}
}
// Print the minimum T required
document.write(lb);
}
// Driver Code
let d = 2;
let arr = [ 1, 1, 1, 1, 1 ];
let n = arr.length;
// Function call
calcT(n, d, arr);
</script>
Producción
3
Complejidad temporal: O( N*log(suma) )
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por deepaksati y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA