Dados dos enteros X e Y y un arreglo binario arr[] de longitud N cuyo primer y último elemento es 1 , la tarea es minimizar el costo de convertir todos los elementos del arreglo a 0 , donde X e Y representan el costo de convertir un subarreglo de todos los 1 s a 0 s y el costo de convertir cualquier elemento a 0 respectivamente.
Ejemplos:
Entrada: arr[] = {1, 1, 1, 0, 1, 1}, X = 10, Y = 4
Salida: 14
Explicación: Para minimizar el costo de convertir todos los elementos a 0, realice las siguientes operaciones:
- Cambie el elemento en el índice 3 a 1. Ahora la array se modifica a {1, 1, 1, 1, 1, 1}. El coste de esta operación es de 4.
- Cambie todos los elementos de la array a 0. El costo de esta operación es 10.
Por lo tanto, el costo total es 4 + 10 + 14.Entrada: arr[] = {1, 0, 0, 1, 1, 0, 1}, X = 2, Y = 3
Salida: 6
Explicación: Para minimizar el costo de cambiar todos los elementos de la array a 0, realice las siguientes operaciones :
- Cambie todos los elementos del subarreglo sobre el rango [3, 4] a 0. Ahora el arreglo se modifica a {1, 0, 0, 0, 0, 0, 1}. El costo de esta operación es de 2.
- Cambie todos los elementos del subarreglo sobre el rango [0, 0] a 0. Ahora el arreglo se modifica a {0, 0, 0, 0, 0, 0, 1}. El costo de esta operación es de 2.
- Cambie todos los elementos del subarreglo sobre el rango [6, 6] a 0. Ahora el arreglo se modifica a {0, 0, 0, 0, 0, 0, 0}. El costo de esta operación es de 2.
Por lo tanto, el costo total es 2 + 2 + 2 = 3.
Enfoque: Siga los pasos:
- Inicialice una variable, digamos ans , para almacenar el costo mínimo de convertir todos los elementos de la array a 0 .
- Calcule y almacene las longitudes de todos los subarreglos que consisten solo en 0 s y guárdelo en un vector y clasifique el vector en orden creciente .
- Ahora, cuente el número de subarreglos que consisten solo en 1 s.
- Recorra la array dada usando la variable i , donde i representa el número de operaciones de costo Y , y realice lo siguiente:
- Para cada número posible de operaciones de costo Y , encuentre el costo realizando X operaciones.
- Dado que, al establecer bits entre dos grupos de 1 , el número total de grupos disminuye, primero combine los dos grupos de 1 consecutivos para reducir el número mínimo de operaciones.
- Encuentre el costo mínimo de completar el paso anterior para cada índice como currCost y actualice ans para almacenar el mínimo de ans y currCost .
- Después de completar los pasos anteriores, imprima el valor de ans como el costo mínimo.
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 calculate the minimum cost
// of converting all array elements to 0s
void minimumCost(int* binary, int n,
int a, int b)
{
// Stores subarrays of 0s only
vector<int> groupOfZeros;
int len = 0, i = 0;
bool increment_need = true;
// Traverse the array
while (i < n) {
increment_need = true;
// If consecutive 0s occur
while (i < n && binary[i] == 0) {
len++;
i++;
increment_need = false;
}
// Increment if needed
if (increment_need == true) {
i++;
}
// Push the current length of
// consecutive 0s in a vector
if (len != 0) {
groupOfZeros.push_back(len);
}
// Update lengths as 0
len = 0;
}
// Sorting vector
sort(groupOfZeros.begin(),
groupOfZeros.end());
i = 0;
bool found_ones = false;
// Stores the number of
// subarrays consisting of 1s
int NumOfOnes = 0;
// Traverse the array
while (i < n) {
found_ones = false;
// If current element is 1
while (i < n && binary[i] == 1) {
i++;
found_ones = true;
}
if (found_ones == false)
i++;
// Otherwise
else
// Increment count of
// consecutive ones
NumOfOnes++;
}
// Stores the minimum cost
int ans = INT_MAX;
// Traverse the array
for (int i = 0; i < n; i++) {
int curr = 0, totalOnes = NumOfOnes;
// First element
if (i == 0) {
curr = totalOnes * a;
}
else {
int mark = i, num_of_changes = 0;
// Traverse the subarray sizes
for (int x : groupOfZeros) {
if (mark >= x) {
totalOnes--;
mark -= x;
// Update cost
num_of_changes += x;
}
else {
break;
}
}
// Cost of performing X
// and Y operations
curr = (num_of_changes * b)
+ (totalOnes * a);
}
// Find the minimum cost
ans = min(ans, curr);
}
// Print the minimum cost
cout << ans;
}
// Driver Code
int main()
{
int arr[] = { 1, 1, 1, 0, 1, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
int X = 10, Y = 4;
// Function Call
minimumCost(arr, N, X, Y);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to calculate the minimum cost
// of converting all array elements to 0s
public static void minimumCost(int[] binary, int n,
int a, int b)
{
// Stores subarrays of 0s only
List<Integer> groupOfZeros = new ArrayList<Integer>();
int len = 0, i = 0;
boolean increment_need = true;
// Traverse the array
while (i < n)
{
increment_need = true;
// If consecutive 0s occur
while (i < n && binary[i] == 0)
{
len++;
i++;
increment_need = false;
}
// Increment if needed
if (increment_need == true)
{
i++;
}
// Push the current length of
// consecutive 0s in a vector
if (len != 0)
{
groupOfZeros.add(len);
}
// Update lengths as 0
len = 0;
}
// Sorting List
Collections.sort(groupOfZeros);
i = 0;
boolean found_ones = false;
// Stores the number of
// subarrays consisting of 1s
int NumOfOnes = 0;
// Traverse the array
while (i < n)
{
found_ones = false;
// If current element is 1
while (i < n && binary[i] == 1)
{
i++;
found_ones = true;
}
if (found_ones == false)
i++;
// Otherwise
else
// Increment count of
// consecutive ones
NumOfOnes++;
}
// Stores the minimum cost
int ans = Integer.MAX_VALUE;
// Traverse the array
for(int i1 = 0; i1 < n; i1++)
{
int curr = 0, totalOnes = NumOfOnes;
// First element
if (i1 == 0)
{
curr = totalOnes * a;
}
else
{
int mark = i1, num_of_changes = 0;
// Traverse the subarray sizes
for(int x : groupOfZeros)
{
if (mark >= x)
{
totalOnes--;
mark -= x;
// Update cost
num_of_changes += x;
}
else
{
break;
}
}
// Cost of performing X
// and Y operations
curr = (num_of_changes * b) +
(totalOnes * a);
}
// Find the minimum cost
ans = Math.min(ans, curr);
}
// Print the minimum cost
System.out.println(ans);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 1, 1, 0, 1, 1 };
int N = 6;
int X = 10, Y = 4;
// Function Call
minimumCost(arr, N, X, Y);
}
}
// This code is contributed by RohitOberoi
Python3
# Python3 program for the above approach import sys # Function to calculate the minimum cost # of converting all array elements to 0s def minimumCost(binary, n, a, b): # Stores subarrays of 0s only groupOfZeros = [] length = 0 i = 0 increment_need = True # Traverse the array while (i < n): increment_need = True # If consecutive 0s occur while (i < n and binary[i] == 0): length += 1 i += 1 increment_need = False # Increment if needed if (increment_need == True): i += 1 # Push the current length of # consecutive 0s in a vector if (length != 0): groupOfZeros.append(length) # Update lengths as 0 length = 0 # Sorting vector groupOfZeros.sort() i = 0 found_ones = False # Stores the number of # subarrays consisting of 1s NumOfOnes = 0 # Traverse the array while (i < n): found_ones = False # If current element is 1 while (i < n and binary[i] == 1): i += 1 found_ones = True if (found_ones == False): i += 1 # Otherwise else: # Increment count of # consecutive ones NumOfOnes += 1 # Stores the minimum cost ans = sys.maxsize # Traverse the array for i in range(n): curr = 0 totalOnes = NumOfOnes # First element if (i == 0): curr = totalOnes * a else: mark = i num_of_changes = 0 # Traverse the subarray sizes for x in groupOfZeros: if (mark >= x): totalOnes -= 1 mark -= x # Update cost num_of_changes += x else: break # Cost of performing X # and Y operations curr = ((num_of_changes * b) + (totalOnes * a)) # Find the minimum cost ans = min(ans, curr) # Print the minimum cost print(ans) # Driver Code if __name__ == "__main__": arr = [1, 1, 1, 0, 1, 1] N = len(arr) X = 10 Y = 4 # Function Call minimumCost(arr, N, X, Y) # This code is contributed by chitranayal
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to calculate the minimum cost
// of converting all array elements to 0s
public static void minimumCost(int[] binary, int n,
int a, int b)
{
// Stores subarrays of 0s only
List<int> groupOfZeros = new List<int>();
int len = 0, i = 0;
bool increment_need = true;
// Traverse the array
while (i < n)
{
increment_need = true;
// If consecutive 0s occur
while (i < n && binary[i] == 0)
{
len++;
i++;
increment_need = false;
}
// Increment if needed
if (increment_need == true)
{
i++;
}
// Push the current length of
// consecutive 0s in a vector
if (len != 0)
{
groupOfZeros.Add(len);
}
// Update lengths as 0
len = 0;
}
// Sorting List
groupOfZeros.Sort();
i = 0;
bool found_ones = false;
// Stores the number of
// subarrays consisting of 1s
int NumOfOnes = 0;
// Traverse the array
while (i < n)
{
found_ones = false;
// If current element is 1
while (i < n && binary[i] == 1)
{
i++;
found_ones = true;
}
if (found_ones == false)
i++;
// Otherwise
else
// Increment count of
// consecutive ones
NumOfOnes++;
}
// Stores the minimum cost
int ans = int.MaxValue;
// Traverse the array
for(int i1 = 0; i1 < n; i1++)
{
int curr = 0, totalOnes = NumOfOnes;
// First element
if (i1 == 0)
{
curr = totalOnes * a;
}
else
{
int mark = i1, num_of_changes = 0;
// Traverse the subarray sizes
foreach(int x in groupOfZeros)
{
if (mark >= x)
{
totalOnes--;
mark -= x;
// Update cost
num_of_changes += x;
}
else
{
break;
}
}
// Cost of performing X
// and Y operations
curr = (num_of_changes * b) +
(totalOnes * a);
}
// Find the minimum cost
ans = Math.Min(ans, curr);
}
// Print the minimum cost
Console.WriteLine(ans);
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 1, 1, 1, 0, 1, 1 };
int N = 6;
int X = 10, Y = 4;
// Function Call
minimumCost(arr, N, X, Y);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program for the above approach
// Function to calculate the minimum cost
// of converting all array elements to 0s
function minimumCost(binary, n, a, b)
{
// Stores subarrays of 0s only
var groupOfZeros = [];
var len = 0, i = 0;
var increment_need = true;
// Traverse the array
while (i < n) {
increment_need = true;
// If consecutive 0s occur
while (i < n && binary[i] == 0) {
len++;
i++;
increment_need = false;
}
// Increment if needed
if (increment_need == true) {
i++;
}
// Push the current length of
// consecutive 0s in a vector
if (len != 0) {
groupOfZeros.push(len);
}
// Update lengths as 0
len = 0;
}
// Sorting vector
groupOfZeros.sort((a,b)=>a-b);
i = 0;
var found_ones = false;
// Stores the number of
// subarrays consisting of 1s
var NumOfOnes = 0;
// Traverse the array
while (i < n) {
found_ones = false;
// If current element is 1
while (i < n && binary[i] == 1) {
i++;
found_ones = true;
}
if (found_ones == false)
i++;
// Otherwise
else
// Increment count of
// consecutive ones
NumOfOnes++;
}
// Stores the minimum cost
var ans = 1000000000;
// Traverse the array
for (var i = 0; i < n; i++) {
var curr = 0, totalOnes = NumOfOnes;
// First element
if (i == 0) {
curr = totalOnes * a;
}
else {
var mark = i, num_of_changes = 0;
// Traverse the subarray sizes
groupOfZeros.forEach(x => {
if (mark >= x) {
totalOnes--;
mark -= x;
// Update cost
num_of_changes += x;
}
});
// Cost of performing X
// and Y operations
curr = (num_of_changes * b)
+ (totalOnes * a);
}
// Find the minimum cost
ans = Math.min(ans, curr);
}
// Print the minimum cost
document.write( ans);
}
// Driver Code
var arr = [ 1, 1, 1, 0, 1, 1 ];
var N = arr.length;
var X = 10, Y = 4;
// Function Call
minimumCost(arr, N, X, Y);
</script>
Producción:
14
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por RohitOberoi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA