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 K – V[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