Dada una array arr[] de tamaño N y un número entero K , la tarea es dividir la array dada en el máximo posible de subarreglos que tengan el mismo número de elementos pares e impares de modo que el costo de dividir la array no exceda K .
El costo de dividir una array en un subarreglo es la diferencia entre el último y el primer elemento de los subarreglos, respectivamente.
Ejemplos:
Entrada: arr[] = {1, 2, 5, 10, 15, 20}, K = 4
Salida: 1
Explicación:
la forma óptima es dividir la array entre 2 y 5.
Entonces se divide en {1, 2} y {5, 10, 15, 20}.
Además, ambos subarreglos contienen el mismo número de elementos pares e impares. El costo de la división es abs(2 – 5) = 3 que es ≤ K.
Entrada: arr[] = {1, 2, 3, 4, 5, 6}, K = 100
Salida: 2
Explicación:
La forma óptima es hacer dos divisiones tales que los subarreglos formados sean {1, 2}, {3, 4}, {5, 6}.
El costo total es abs(2 – 3) + abs(4 – 5) = 2
Enfoque ingenuo: el enfoque más simple para resolver este problema es el siguiente:
- Divida la array en cada índice y verifique si el costo es menor que K o no.
- Si el costo es menor que K , verifique si el número de elementos pares e impares en el subarreglo es igual o no.
- Ahora compruebe si es posible o no otra división repitiendo los mismos pasos.
- Después de verificar todas las divisiones posibles, imprima el costo mínimo que sume una suma menor que K .
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque Eficiente: La idea es mantener los contadores que almacenan el número de números pares e impares en el arreglo. A continuación se muestran los pasos:
- Inicialice una array (digamos poss[] ) que almacena el costo de todas las divisiones posibles.
- Atraviesa la array arr[] . Para cada índice, compruebe si el subarreglo hasta este índice y el subarreglo que comienza en el siguiente índice tienen el mismo número de elementos pares e impares.
- Si se cumple la condición anterior, entonces es posible una división. Almacene el costo asociado con esta división en poss[] .
- Repita los pasos anteriores para todos los elementos de la array y almacene los costos de cada división.
- El costo de división en el índice i se puede obtener mediante abs(arr[i + 1] – arr[i]) .
- Ahora, para encontrar el número máximo de divisiones posibles, ordene la array poss[] que contiene los costos de cada división posible.
- Ahora seleccione todos los costos mínimos de poss[] cuya suma sea menor o igual a K .
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 cost of
// splitting the arrays into subarray
// with cost less than K
int make_cuts(int arr[], int n, int K)
{
// Store the possible splits
int ans = 0;
// Stores the cost of each split
vector<int> poss;
// Stores the count of even numbers
int ce = 0;
// Stores the count
// of odd numbers
int co = 0;
for (int x = 0; x < n - 1; x++) {
// Count of odd & even elements
if (arr[x] % 2 == 0)
ce++;
else
co++;
// Check the required conditions
// for a valid split
if (ce == co && co > 0
&& ce > 0) {
poss.push_back(
abs(arr[x]
- arr[x + 1]));
}
}
// Sort the cost of splits
sort(poss.begin(), poss.end());
// Find the minimum split costs
// adding up to sum less than K
for (int x : poss) {
if (K >= x) {
ans++;
K -= x;
}
else
break;
}
return ans;
}
// Driver Code
int main()
{
// Given array and K
int N = 6;
int K = 4;
int arr[] = { 1, 2, 5, 10, 15, 20 };
// Function Call
cout << make_cuts(arr, N, K);
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the cost of
// splitting the arrays into subarray
// with cost less than K
static int make_cuts(int arr[], int n, int K)
{
// Store the possible splits
int ans = 0;
// Stores the cost of each split
Vector<Integer> poss = new Vector<Integer>();
// Stores the count of even numbers
int ce = 0;
// Stores the count
// of odd numbers
int co = 0;
for(int x = 0; x < n - 1; x++)
{
// Count of odd & even elements
if (arr[x] % 2 == 0)
ce++;
else
co++;
// Check the required conditions
// for a valid split
if (ce == co && co > 0 && ce > 0)
{
poss.add(Math.abs(arr[x] -
arr[x + 1]));
}
}
// Sort the cost of splits
Collections.sort(poss);
// Find the minimum split costs
// adding up to sum less than K
for(int x : poss)
{
if (K >= x)
{
ans++;
K -= x;
}
else
break;
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given array and K
int N = 6;
int K = 4;
int arr[] = { 1, 2, 5, 10, 15, 20 };
// Function call
System.out.print(make_cuts(arr, N, K));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach # Function to find the cost of # splitting the arrays into subarray # with cost less than K def make_cuts(arr, n, K): # Store the possible splits ans = 0 # Stores the cost of each split poss = [] # Stores the count of even numbers ce = 0 # Stores the count # of odd numbers co = 0 for x in range(n - 1): # Count of odd & even elements if(arr[x] % 2 == 0): ce += 1 else: co += 1 # Check the required conditions # for a valid split if(ce == co and co > 0 and ce > 0): poss.append(abs(arr[x] - arr[x + 1])) # Sort the cost of splits poss.sort() # Find the minimum split costs # adding up to sum less than K for x in poss: if (K >= x): ans += 1 K -= x else: break return ans # Driver Code # Given array and K N = 6 K = 4 arr = [ 1, 2, 5, 10, 15, 20 ] # Function call print(make_cuts(arr, N, K)) # This code is contributed by Shivam Singh
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the cost of
// splitting the arrays into subarray
// with cost less than K
static int make_cuts(int []arr, int n, int K)
{
// Store the possible splits
int ans = 0;
// Stores the cost of each split
List<int> poss = new List<int>();
// Stores the count of even numbers
int ce = 0;
// Stores the count
// of odd numbers
int co = 0;
for(int x = 0; x < n - 1; x++)
{
// Count of odd & even elements
if (arr[x] % 2 == 0)
ce++;
else
co++;
// Check the required conditions
// for a valid split
if (ce == co && co > 0 && ce > 0)
{
poss.Add(Math.Abs(arr[x] -
arr[x + 1]));
}
}
// Sort the cost of splits
poss.Sort();
// Find the minimum split costs
// adding up to sum less than K
foreach(int x in poss)
{
if (K >= x)
{
ans++;
K -= x;
}
else
break;
}
return ans;
}
// Driver Code
public static void Main(String[] args)
{
// Given array and K
int N = 6;
int K = 4;
int []arr = { 1, 2, 5, 10, 15, 20 };
// Function call
Console.Write(make_cuts(arr, N, K));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program for the above approach
// Function to find the cost of
// splitting the arrays into subarray
// with cost less than K
function make_cuts(arr, n, K)
{
// Store the possible splits
var ans = 0;
// Stores the cost of each split
var poss = [];
// Stores the count of even numbers
var ce = 0;
// Stores the count
// of odd numbers
var co = 0;
var x;
for (x = 0; x < n - 1; x++) {
// Count of odd & even elements
if (arr[x] % 2 == 0)
ce++;
else
co++;
// Check the required conditions
// for a valid split
if (ce == co && co > 0
&& ce > 0) {
poss.push(
Math.abs(arr[x]
- arr[x + 1]));
}
}
// Sort the cost of splits
poss.sort();
var i;
// Find the minimum split costs
// adding up to sum less than K
for(i=0;i<poss.length;i++){
if (K >= poss[i]) {
ans++;
K -= poss[i];
}
else
break;
}
return ans;
}
// Driver Code
// Given array and K
var N = 6;
var K = 4;
var arr = [1, 2, 5, 10, 15, 20];
// Function Call
document.write(make_cuts(arr, N, K));
// This code is contributed by bgangwar59.
</script>
Producción:
1
Complejidad de tiempo: O(N log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shobhitgupta907 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA