Particiones máximas posibles de una array dada con un costo como máximo K y un recuento igual de elementos pares e impares

Dados dos enteros N, K y un arreglo , arr[] de tamaño N, que contiene un número igual de elementos pares e impares, y también dado que el costo de dividir el arreglo haciendo un corte entre el índice i  y i+1 es igual a abs(arr[i]-arr[i+1]) , la tarea es encontrar las particiones máximas de la array, de modo que cada partición tenga el mismo número de elementos pares e impares y tenga un costo total menor que o igual a K.

Ejemplos:

Entrada: N = 6, K = 4, arr[] = {1, 2, 5, 10, 15, 20}
Salida: 1
Explicación: 
La única forma posible de dividir es haciendo un corte entre el índice 1 y el índice 2. 
Costo de partición = |arr[1]( =2)- arr[2](= 5)| = 3, que es menor e igual a K 
Arreglos después de la partición: {1, 2} y {5, 10, 15, 20}.

Entrada: N = 4, K = 10, arr[] = {1, 3, 2, 4}
Salida: 0

Enfoque: El problema dado se puede resolver en base a las observaciones de que siempre es posible hacer una partición válida haciendo un corte entre el índice i y i+i, si el número de elementos pares e impares en el prefijo de i es igual. Siga los pasos para resolver el problema.

  • Inicialice un vector V para almacenar los costos de todos los cortes posibles en la array.
  • Además, inicialice las variables, diga impar como 0 e incluso como 0 , que almacenan el recuento de elementos pares e impares.
  • Recorra el arreglo arr[], usando la variable i y realice los siguientes pasos:
    • Si el elemento actual es impar, incremente impar en 1. De lo contrario, incremente par en 1.
    • Si el valor de impar es igual al valor de par , agregue el valor de | arr[i]arr[i+1] | a v
  • Ordena el vector V en orden ascendente.
  • Inicialice una variable entera como 1 , para almacenar el número de particiones de la array.
  • Recorra el vector V, usando la variable i y realice los siguientes pasos:
    • Si el valor de V[i] es menor o igual que K , actualice el valor K como KV[i] e incremente ans en 1.
    • De lo contrario, sal del bucle .
  • Finalmente, después de completar los pasos anteriores, imprima el valor de ans como la respuesta obtenida.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum
// partitions of the array with
// equal even and odd elements
// with cost less than k
int maximumcut(int arr[], int N, int K)
{
    // Stores count of odd elements
    int odd = 0;
    // Stores count of even elements
    int even = 0;
 
    // Stores the cost of partitions
    vector<int> V;
 
    for (int i = 0; i < N - 1; i++) {
        // Odd element
        if (arr[i] % 2 == 1) {
            odd++;
        }
        // Even element
        else {
            even++;
        }
 
        // Partition is possible
        if (odd == even) {
            int cost = abs(arr[i] - arr[i + 1]);
 
            // Append the cost of partition
            V.push_back(cost);
        }
    }
    // Stores the maximum number of
    // partitions
    int ans = 0;
 
    // Sort the costs in ascending order
    sort(V.begin(), V.end());
 
    // Traverse the vector V
    for (int i = 0; i < V.size(); i++) {
        // Check if cost is less than K
        if (V[i] <= K) {
            // Update the value of K
            K = K - V[i];
 
            // Update the value of ans
            ans++;
        }
        else {
            break;
        }
    }
    // Return ans
    return ans;
}
 
// Driver code
int main()
{
    // Given Input
    int arr[] = {1, 2, 5, 10, 15, 20};
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 4;
    // Function call
    cout << maximumcut(arr, N, K);
    return 0;
}

Java

// Java code for the above approach
import java.util.ArrayList;
import java.util.Arrays;
 
class GFG
{
   
// Function to find the maximum
// partitions of the array with
// equal even and odd elements
// with cost less than k
public static int maximumcut(int arr[], int N, int K)
{
   
    // Stores count of odd elements
    int odd = 0;
   
    // Stores count of even elements
    int even = 0;
 
    // Stores the cost of partitions
    ArrayList<Integer> V = new ArrayList<Integer>();
 
    for (int i = 0; i < N - 1; i++) {
        // Odd element
        if (arr[i] % 2 == 1) {
            odd++;
        }
        // Even element
        else {
            even++;
        }
 
        // Partition is possible
        if (odd == even) {
            int cost = Math.abs(arr[i] - arr[i + 1]);
 
            // Append the cost of partition
            V.add(cost);
        }
    }
    // Stores the maximum number of
    // partitions
    int ans = 0;
 
    // Sort the costs in ascending order
    V.sort(null);
 
    // Traverse the vector V
    for (int i = 0; i < V.size(); i++)
    {
       
        // Check if cost is less than K
        if (V.get(i) <= K)
        {
           
            // Update the value of K
            K = K - V.get(i);
 
            // Update the value of ans
            ans++;
        }
        else {
            break;
        }
    }
    // Return ans
    return ans;
}
 
// Driver code
public static void  main(String args[])
{
    // Given Input
    int arr[] = {1, 2, 5, 10, 15, 20};
    int N = arr.length;
    int K = 4;
    // Function call
    System.out.println(maximumcut(arr, N, K));
}
 
}
 
// This code is contributed by gfgking.

Python3

# Python3 code for the above approach
 
# Function to find the maximum
# partitions of the array with
# equal even and odd elements
# with cost less than k
def maximumcut(arr, N, K):
     
    # Stores count of odd elements
    odd = 0
     
    # Stores count of even elements
    even = 0
 
    # Stores the cost of partitions
    V = []
 
    for i in range(0, N - 1, 1):
         
        # Odd element
        if (arr[i] % 2 == 1):
            odd += 1
 
        # Even element
        else:
            even += 1
 
        # Partition is possible
        if (odd == even):
            cost = abs(arr[i] - arr[i + 1])
 
            # Append the cost of partition
            V.append(cost)
 
    # Stores the maximum number of
    # partitions
    ans = 0
 
    # Sort the costs in ascending order
    V.sort()
 
    # Traverse the vector V
    for i in range(len(V)):
         
        # Check if cost is less than K
        if (V[i] <= K):
             
            # Update the value of K
            K = K - V[i]
 
            # Update the value of ans
            ans += 1
             
        else:
            break
 
    # Return ans
    return ans
 
# Driver code
if __name__ == '__main__':
     
    # Given Input
    arr = [ 1, 2, 5, 10, 15, 20 ]
    N = len(arr)
    K = 4
     
    # Function call
    print(maximumcut(arr, N, K))
     
# This code is contributed by SURENDRA_GANGWAR

C#

// C# code for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
  
// Function to find the maximum
// partitions of the array with
// equal even and odd elements
// with cost less than k
static int maximumcut(int []arr, int N, int K)
{
     
    // Stores count of odd elements
    int odd = 0;
     
    // Stores count of even elements
    int even = 0;
 
    // Stores the cost of partitions
    List<int> V = new List<int>();
 
    for(int i = 0; i < N - 1; i++)
    {
         
        // Odd element
        if (arr[i] % 2 == 1)
        {
            odd++;
        }
         
        // Even element
        else
        {
            even++;
        }
 
        // Partition is possible
        if (odd == even)
        {
            int cost = Math.Abs(arr[i] - arr[i + 1]);
 
            // Append the cost of partition
            V.Add(cost);
        }
    }
     
    // Stores the maximum number of
    // partitions
    int ans = 0;
 
    // Sort the costs in ascending order
    V.Sort();
 
    // Traverse the vector V
    for(int i = 0; i < V.Count; i++)
    {
         
        // Check if cost is less than K
        if (V[i] <= K)
        {
             
            // Update the value of K
            K = K - V[i];
 
            // Update the value of ans
            ans++;
        }
        else
        {
            break;
        }
    }
     
    // Return ans
    return ans;
}
 
// Driver code
public static void Main()
{
     
    // Given Input
    int []arr = { 1, 2, 5, 10, 15, 20 };
    int N = arr.Length;
    int K = 4;
     
    // Function call
    Console.Write(maximumcut(arr, N, K));
}
}
 
// This code is contributed by ipg2016107

Javascript

<script>
  
        // JavaScript code for the above approach
 
        // Function to find the maximum
        // partitions of the array with
        // equal even and odd elements
        // with cost less than k
        function maximumcut(arr, N, K) {
            // Stores count of odd elements
            let odd = 0;
            // Stores count of even elements
            let even = 0;
 
            // Stores the cost of partitions
            var V = [];
 
            for (let i = 0; i < N - 1; i++) {
                // Odd element
                if (arr[i] % 2 == 1) {
                    odd++;
                }
                // Even element
                else {
                    even++;
                }
 
                // Partition is possible
                if (odd == even) {
                    let cost = Math.abs(arr[i] - arr[i + 1]);
 
                    // Append the cost of partition
                    V.push(cost);
                }
            }
            // Stores the maximum number of
            // partitions
            let ans = 0;
 
            // Sort the costs in ascending order
            V.sort();
 
            // Traverse the vector V
            for (let i = 0; i < V.length; i++) {
                // Check if cost is less than K
                if (V[i] <= K) {
                    // Update the value of K
                    K = K - V[i];
 
                    // Update the value of ans
                    ans++;
                }
                else {
                    break;
                }
            }
            // Return ans
            return ans;
        }
 
        // Driver code
 
        // Given Input
        let arr = [1, 2, 5, 10, 15, 20];
        let N = arr.length;
        let K = 4;
        // Function call
        document.write(maximumcut(arr, N, K));
         
// This code is contributed by Potta Lokesh
 
</script>
Producción: 

1

 

Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por jainprateekjain2001 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *