Dada la string binaria str y los enteros A , que denota el costo de convertir 1 s consecutivos en 0 s, y B , que denota el costo de convertir 0 s en 1 s. La tarea es encontrar el costo mínimo para reducir la string str a 0 s solamente.
Ejemplos:
Entrada: str = “01101110”, A = 5, B = 1
Salida: 6
Explicación:
Convierta str[3] a ‘1’ . Costo = 1, str = «01111110».
Convierta la substring {str[1], … str[6]} a ‘0’ . Costo = 5, str = “00000000”.Entrada: str = “1010010011110111”, A = 12, B = 14
Salida: 60
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
Para cualquier par de segmentos consecutivos de 1 s [L1, R1] y [L2, R2] (donde L2 > R1 ), elija convertir ambos segmentos a 0 s por un costo de 2 * A o convertir 0 s entre ambos segmentos a 1 s y convertir [L1, R2] a 1 s por un costo de A + (L2 – R1 – 1) * B .
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable left_1 y almacene el índice del ‘1’ más a la izquierda en str
- Inicialice otra variable right_1 y almacene el índice del ‘1’ más a la derecha en str .
- Si left_1 y right_1 no existen, entonces str ya consta de 0 s solamente. Por lo tanto, imprima 0 como el costo mínimo
- De lo contrario, hay al menos un ‘1’ en str . Por lo tanto, inicialice el costo = A .
- Iterar sobre los caracteres en la string str de left_1 a right_1 con un puntero i
- Calcule el número de 0 s consecutivos a la derecha de i y guárdelo en ceros variables .
- Si la longitud de los ceros excede 0 , convierta 0 s en 1 s por un costo de ceros * B o convierta 1 s consecutivos en 0 s por el costo de A .
- Por lo tanto, incremente el costo por min (ceros * B, A)
- Finalmente, imprima el costo mínimo obtenido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <iostream>
using namespace std;
// Function to find the minimum cost
// to convert given string to 0s only
void convert_to_allzeroes(string str,
int a, int b)
{
// Length of string
int len = str.length();
// Stores the index of leftmost '1' in str
int left_1, i = 0;
while (i < len && str[i] == '0')
i++;
// Update the index of leftmost '1' in str
left_1 = i;
// Stores the index of rightmost '1' in str
int right_1;
i = len - 1;
while (i >= 0 && str[i] == '0')
i--;
// Update the index of rightmost '1' in str
right_1 = i;
// If str does not contain any '1's
if (left_1 == len && right_1 == -1) {
// No changes required
cout << 0;
return;
}
// Stores minimum cost
int cost = a, zeroes;
// Iterating through str form
// left_1 to right_1
for (i = left_1; i <= right_1; i++) {
// Stores length of
// consecutive 0s
zeroes = 0;
// Calculate length of consecutive 0s
while (i < len && str[i] == '0') {
zeroes++;
i++;
}
// If a substring of 0s exists
if (zeroes)
// Update minimum cost
cost += min(zeroes * b, a);
}
// Printing the minimum cost
cout << cost;
}
// Driver Code
int main()
{
string str = "01101110";
int A = 5, B = 1;
convert_to_allzeroes(str, A, B);
return 0;
}
Java
// Java program to implement
// the above approach
class GFG{
// Function to find the minimum cost
// to convert given string to 0s only
public static void convert_to_allzeroes(String str,
int a, int b)
{
// Length of string
int len = str.length();
// Stores the index of leftmost '1' in str
int left_1, i = 0;
while (i < len && str.charAt(i) == '0')
i++;
// Update the index of leftmost '1' in str
left_1 = i;
// Stores the index of rightmost '1' in str
int right_1;
i = len - 1;
while (i >= 0 && str.charAt(i) == '0')
i--;
// Update the index of rightmost '1' in str
right_1 = i;
// If str does not contain any '1's
if (left_1 == len && right_1 == -1)
{
// No changes required
System.out.print(0);
return;
}
// Stores minimum cost
int cost = a, zeroes;
// Iterating through str form
// left_1 to right_1
for(i = left_1; i <= right_1; i++)
{
// Stores length of
// consecutive 0s
zeroes = 0;
// Calculate length of consecutive 0s
while (i < len && str.charAt(i) == '0')
{
zeroes++;
i++;
}
// If a substring of 0s exists
if (zeroes != 0)
// Update minimum cost
cost += Math.min(zeroes * b, a);
}
// Printing the minimum cost
System.out.print(cost);
}
// Driver code
public static void main(String[] args)
{
String str = "01101110";
int A = 5, B = 1;
convert_to_allzeroes(str, A, B);
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 Program to implement # the above approach # Function to find the minimum # cost to convert given string # to 0s only def convert_to_allzeroes(st, a, b): # Length of string length = len(st) # Stores the index of # leftmost '1' in str left_1 = 0 i = 0 while (i < length and st[i] == '0'): i += 1 # Update the index of # leftmost '1' in str left_1 = i # Stores the index of # rightmost '1' in str right_1 = 0 i = length - 1 while (i >= 0 and st[i] == '0'): i -= 1 # Update the index of # rightmost '1' in str right_1 = i # If str does not contain # any '1's if (left_1 == length and right_1 == -1): # No changes required print(0) return # Stores minimum cost cost = a # Iterating through str form # left_1 to right_1 for i in range(left_1, right_1 + 1): # Stores length of # consecutive 0s zeroes = 0 # Calculate length of # consecutive 0s while (i < length and st[i] == '0'): zeroes += 1 i += 1 # If a substring of # 0s exists if (zeroes): # Update minimum cost cost += min(zeroes * b, a) # Printing the minimum cost print(cost) # Driver Code if __name__ == "__main__": st = "01101110" A = 5 B = 1 convert_to_allzeroes(st, A, B) # This code is contributed by Chitranayal
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to find the minimum cost
// to convert given string to 0s only
public static void convert_to_allzeroes(string str,
int a, int b)
{
// Length of string
int len = str.Length;
// Stores the index of leftmost '1' in str
int left_1, i = 0;
while (i < len && str[i] == '0')
i++;
// Update the index of leftmost '1' in str
left_1 = i;
// Stores the index of rightmost '1' in str
int right_1;
i = len - 1;
while (i >= 0 && str[i] == '0')
i--;
// Update the index of rightmost '1' in str
right_1 = i;
// If str does not contain any '1's
if (left_1 == len && right_1 == -1)
{
// No changes required
Console.Write(0);
return;
}
// Stores minimum cost
int cost = a, zeroes;
// Iterating through str form
// left_1 to right_1
for(i = left_1; i <= right_1; i++)
{
// Stores length of
// consecutive 0s
zeroes = 0;
// Calculate length of consecutive 0s
while (i < len && str[i] == '0')
{
zeroes++;
i++;
}
// If a substring of 0s exists
if (zeroes != 0)
// Update minimum cost
cost += Math.Min(zeroes * b, a);
}
// Printing the minimum cost
Console.Write(cost);
}
// Driver code
public static void Main()
{
string str = "01101110";
int A = 5, B = 1;
convert_to_allzeroes(str, A, B);
}
}
// This code is contributed by susmitakundugoaldanga
Javascript
<script>
// JavaScript program for the above approach
// Function to find the minimum cost
// to convert given string to 0s only
function convert_to_allzeroes(str, a, b)
{
// Length of string
let len = str.length;
// Stores the index of leftmost '1' in str
let left_1, i = 0;
while (i < len && str[i] == '0')
i++;
// Update the index of leftmost '1' in str
left_1 = i;
// Stores the index of rightmost '1' in str
let right_1;
i = len - 1;
while (i >= 0 && str[i] == '0')
i--;
// Update the index of rightmost '1' in str
right_1 = i;
// If str does not contain any '1's
if (left_1 == len && right_1 == -1)
{
// No changes required
document.write(0);
return;
}
// Stores minimum cost
let cost = a, zeroes;
// Iterating through str form
// left_1 to right_1
for(i = left_1; i <= right_1; i++)
{
// Stores length of
// consecutive 0s
zeroes = 0;
// Calculate length of consecutive 0s
while (i < len && str[i] == '0')
{
zeroes++;
i++;
}
// If a substring of 0s exists
if (zeroes != 0)
// Update minimum cost
cost += Math.min(zeroes * b, a);
}
// Printing the minimum cost
document.write(cost);
}
// Driver Code
let str = "01101110";
let A = 5, B = 1;
convert_to_allzeroes(str, A, B);
</script>
Producción:
6
Complejidad de tiempo: O(N), donde N es la longitud de la string.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA