Dada una string binaria , str , dos arrays de enteros R[] y C[] de tamaño N. Voltear todos los caracteres del índice i a R[i] requiere un costo de C[i] . La tarea es minimizar el costo requerido para convertir la string binaria dada a solo 0s .
Ejemplos:
Entrada: str = “1010”, R[] = {1, 2, 2, 3}, C[] = {3, 1, 2, 3}
Salida: 4
Explicación:
Cambiando todos los caracteres del índice 1 al 2, modifica str a «1100». Por lo tanto, cost = 1
Voltear todos los caracteres del índice 1 al 2, modifica str a «0000». Por lo tanto, costo = costo + 3 = 4
Por lo tanto, el costo mínimo requerido es 4.Entrada: str = “01100”, R[] = {1, 2, 3, 4, 5}, C[] = {1, 5, 5, 2, 3}
Salida: 10
Enfoque : El problema se puede resolver usando la técnica Greedy . La idea es recorrer la string dada de izquierda a derecha y verificar si el carácter actual es un carácter distinto de cero o no. Si se determina que es cierto, cambie todos los caracteres del índice actual (= i) al índice R[i] th . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos flip , para almacenar la cantidad de veces que se puede voltear el carácter actual.
- Cree una cola de prioridad , digamos pq para almacenar el rango de índices de caracteres en el lado derecho del carácter actual cuyo valor de volteo es mayor que 0.
- Inicialice una variable, digamos costo para almacenar el costo mínimo para obtener la string requerida.
- Recorra la string dada y verifique si el carácter actual es ‘ 1 ‘ o no. Si se determina que es cierto, cambie todos los caracteres en el rango i a R[i] e incremente el valor del costo en C[i] .
- Finalmente, imprima el valor del costo .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to get the minimum
// Cost to convert all characters
// of given string to 0s
int minCost(string str, int N, int R[], int C[])
{
// Stores the range of indexes
// of characters that need
// to be flipped
priority_queue<int, vector<int>, greater<int> > pq;
// Stores the number of times
// current character is flipped
int flip = 0;
// Stores minimum cost to get
// the required string
int cost = 0;
// Traverse the given string
for (int i = 0; i < N; i++)
{
// Remove all value from pq
// whose value is less than i
while (pq.size() > 0 and pq.top() < i)
{
pq.pop();
// Update flip
flip--;
}
// If current character
// is flipped odd times
if (flip % 2 == 1)
{
str[i] = '1' - str[i] + '0';
}
// If current character contains
// non-zero value
if (str[i] == '1')
{
// Update flip
flip++;
// Update cost
cost += C[i];
// Append R[i] into pq
pq.push(R[i]);
}
}
return cost;
}
// Driver Code
int main()
{
string str = "1010";
int R[] = { 1, 2, 2, 3 };
int C[] = { 3, 1, 2, 3 };
int N = str.length();
// Function call
cout << minCost(str, N, R, C);
}
Java
// Java program to implement
// the above approach
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG {
// Function to get the minimum
// Cost to convert all characters
// of given string to 0s
public static int minCost(String s,
int R[],
int C[],
int N)
{
char ch[] = s.toCharArray();
// Stores the range of indexes
// of characters that need
// to be flipped
PriorityQueue<Integer> pq = new PriorityQueue<>();
// Stores the number of times
// current character is flipped
int flip = 0;
// Stores minimum cost to get
// the required string
int cost = 0;
// Traverse the given string
for (int i = 0; i < N; i++) {
// Remove all value from pq
// whose value is less than i
while (pq.size() > 0 && pq.peek() < i)
{
pq.poll();
// Update flip
flip--;
}
// Get the current number
int cn = ch[i] - '0';
// If current character
// is flipped odd times
if (flip % 2 == 1)
cn = 1 - cn;
// If current character contains
// non-zero value
if (cn == 1)
{
// Update flip
flip++;
// Update cost
cost += C[i];
// Append R[i] into pq
pq.add(R[i]);
}
}
return cost;
}
// Driver Code
public static void main(String[] args)
{
int N = 4;
String s = "1010";
int R[] = { 1, 2, 2, 3 };
int C[] = { 3, 1, 2, 3 };
// Function call
System.out.println(minCost(s, R, C, N));
}
}
Python3
# Python3 program to implement
# the above approach
# Function to get the minimum
# Cost to convert all characters
# of given string to 0s
def minCost(s, R, C, N) :
ch = list(s)
# Stores the range of indexes
# of characters that need
# to be flipped
pq = []
# Stores the number of times
# current character is flipped
flip = 0
# Stores minimum cost to get
# the required string
cost = 0
# Traverse the given string
for i in range(N) :
# Remove all value from pq
# whose value is less than i
while (len(pq) > 0 and pq[0] < i) :
pq.pop(0);
# Update flip
flip -= 1
# Get the current number
cn = ord(ch[i]) - ord('0')
# If current character
# is flipped odd times
if (flip % 2 == 1) :
cn = 1 - cn
# If current character contains
# non-zero value
if (cn == 1) :
# Update flip
flip += 1
# Update cost
cost += C[i]
# Append R[i] into pq
pq.append(R[i])
return cost
# Driver code
N = 4
s = "1010"
R = [ 1, 2, 2, 3 ]
C = [ 3, 1, 2, 3 ]
# Function call
print(minCost(s, R, C, N))
# This code is contributed by divyeshrabadiya07.
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to get the minimum
// Cost to convert all characters
// of given string to 0s
public static int minCost(String s, int []R,
int []C, int N)
{
char []ch = s.ToCharArray();
// Stores the range of indexes
// of characters that need
// to be flipped
Queue<int> pq = new Queue<int>();
// Stores the number of times
// current character is flipped
int flip = 0;
// Stores minimum cost to get
// the required string
int cost = 0;
// Traverse the given string
for(int i = 0; i < N; i++)
{
// Remove all value from pq
// whose value is less than i
while (pq.Count > 0 && pq.Peek() < i)
{
pq.Dequeue();
// Update flip
flip--;
}
// Get the current number
int cn = ch[i] - '0';
// If current character
// is flipped odd times
if (flip % 2 == 1)
cn = 1 - cn;
// If current character contains
// non-zero value
if (cn == 1)
{
// Update flip
flip++;
// Update cost
cost += C[i];
// Append R[i] into pq
pq.Enqueue(R[i]);
}
}
return cost;
}
// Driver Code
public static void Main(String[] args)
{
int N = 4;
String s = "1010";
int []R = { 1, 2, 2, 3 };
int []C = { 3, 1, 2, 3 };
// Function call
Console.WriteLine(minCost(s, R, C, N));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to get the minimum
// Cost to convert all characters
// of given string to 0s
function minCost(str, N, R, C)
{
str = str.split('');
// Stores the range of indexes
// of characters that need
// to be flipped
var pq = [];
// Stores the number of times
// current character is flipped
var flip = 0;
// Stores minimum cost to get
// the required string
var cost = 0;
// Traverse the given string
for (var i = 0; i < N; i++)
{
// Remove all value from pq
// whose value is less than i
while (pq.length > 0 && pq[pq.length-1] < i)
{
pq.pop();
// Update flip
flip--;
}
// If current character
// is flipped odd times
if (flip % 2 == 1)
{
str[i] = String.fromCharCode('1'.charCodeAt(0) - str[i].charCodeAt(0) + '0'.charCodeAt(0));
}
// If current character contains
// non-zero value
if (str[i] == '1')
{
// Update flip
flip++;
// Update cost
cost += C[i];
// Append R[i] into pq
pq.push(R[i]);
}
pq.sort((a,b)=>b-a);
}
return cost;
}
// Driver Code
var str = "1010";
var R = [1, 2, 2, 3 ];
var C = [3, 1, 2, 3 ];
var N = str.length;
// Function call
document.write(minCost(str, N, R, C));
// This code is contributed by noob2000.
</script>
Producción
4
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA