Minimice el costo de convertir todos los caracteres de una string binaria a 0

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

Deja una respuesta

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