Minimice el costo de convertir una string dada al tipo XYXY… o XXYY…

Dada una string binaria s y una array ct[] de tamaño par. La tarea es minimizar el costo de las operaciones para:

  • Convierta la string s en una string del tipo XYXYXYXYXY … o XXYYXXYYXXYY
  • En una operación, se permite voltear i -ésimo carácter con costo ct[i] .

Ejemplos

Entrada: s = “1011” ct = {1, 2, 1, 3}
Salida: 1
Explicación: Las siguientes operaciones se realizan para convertir s al formato dado:
Cambie el bit 0 de 1 a 0, el s actualizado = “0011” que tiene la forma XXYY. 
Por lo tanto, 1 es la respuesta que es mínima posible.

Entrada: “1010”
Salida: 0
Explicación: La string ya está en un formato dado. 

 

Enfoque: Este problema está basado en la observación. Siga los pasos a continuación para resolver el problema dado.

  • Solo hay cuatro tipos de strings binarias, según el problema.
    • 010101010101…….
    • 101010101010…….
    • 001100110011……..
    • 110011001100……..
  • Tenemos que verificar solo estas cuatro strings diferentes.
  • Pase la string junto con el costo y los primeros cuatro caracteres esperados.
  • Si los caracteres esperados no coinciden con los caracteres reales de la string, agregue el costo correspondiente al i -ésimo valor.
  • Repita el procedimiento para las cuatro secuencias esperadas y elija el costo mínimo.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
int solve_util(string s, int c[],
               char x, char y,
               char z, char w)
{
    int ans = 0;
    for (int i = 0; i < s.length(); i += 4) {
        if (s[i] != x)
            ans += c[i];
        if (i + 1 < s.length()
            && s[i + 1] != y)
            ans += c[i + 1];
        if (i + 2 < s.length()
            && s[i + 2] != z)
            ans += c[i + 2];
        if (i + 3 < s.length()
            && s[i + 3] != w)
            ans += c[i + 3];
    }
    return ans;
}
 
int solve_util2(string s, int c[],
                char x, char y)
{
    int ans = 0;
    if (s[0] != x)
        ans += c[0];
    if (s[1] != y)
        ans += c[1];
    return ans;
}
 
// Function to convert given
// string to required form
int minOperations(int N, string S, int C[])
{
    // code here
    if (S.length() == 2) {
        int x = solve_util2(
            S, C, '0', '1');
        int y = solve_util2(
            S, C, '1', '0');
        int z = solve_util2(
            S, C, '1', '1');
        int w = solve_util2(
            S, C, '0', '0');
        return min({ x, y, z, w });
    }
    int x = solve_util(
        S, C, '0', '1', '0', '1');
    int y = solve_util(
        S, C, '1', '0', '1', '0');
    int z = solve_util(
        S, C, '1', '1', '0', '0');
    int w = solve_util(
        S, C, '0', '0', '1', '1');
    return min({ x, y, z, w });
}
 
// Driver Code
int main()
{
    int N = 4;
    string s = "1011";
    int ct[] = { 1, 2, 1, 3 };
 
    cout << minOperations(N, s, ct) << "\n";
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
 
  static int solve_util(char s[], int c[],
                        char x, char y,
                        char z, char w)
  {
    int ans = 0;
    for (int i = 0; i < s.length; i += 4) {
      if (s[i] != x)
        ans += c[i];
      if (i + 1 < s.length
          && s[i + 1] != y)
        ans += c[i + 1];
      if (i + 2 < s.length
          && s[i + 2] != z)
        ans += c[i + 2];
      if (i + 3 < s.length
          && s[i + 3] != w)
        ans += c[i + 3];
    }
    return ans;
  }
 
  static int solve_util2(char s[], int c[],
                         char x, char y)
  {
    int ans = 0;
    if (s[0] != x)
      ans += c[0];
    if (s[1] != y)
      ans += c[1];
    return ans;
  }
 
  // Function to convert given
  // string to required form
  static int minOperations(int N, char S[], int C[])
  {
    // code here
    if (S.length == 2) {
      int x = solve_util2(
        S, C, '0', '1');
      int y = solve_util2(
        S, C, '1', '0');
      int z = solve_util2(
        S, C, '1', '1');
      int w = solve_util2(
        S, C, '0', '0');
      return Math.min(x, Math.min( y, Math.min(z, w )));
    }
    int x = solve_util(
      S, C, '0', '1', '0', '1');
    int y = solve_util(
      S, C, '1', '0', '1', '0');
    int z = solve_util(
      S, C, '1', '1', '0', '0');
    int w = solve_util(
      S, C, '0', '0', '1', '1');
    return Math.min(x, Math.min( y, Math.min(z, w )));
  }
 
  // Driver Code
  public static void main (String[] args) {
    int N = 4;
    char s[] = {'1', '0', '1', '1'};
    int ct[] = { 1, 2, 1, 3 };
 
    System.out.print(minOperations(N, s, ct));
  }
}
 
// This code is contributed by hrithikgarg03188.

Python3

# Python program for above approach
def solve_util(s, c, x, y, z, w):
    ans = 0
    for i in range(0, len(s), 4):
        if (s[i] != x):
            ans += c[i]
        if (i + 1 < len(s)
                and s[i + 1] != y):
            ans += c[i + 1]
        if (i + 2 < len(s)
                and s[i + 2] != z):
            ans += c[i + 2]
        if (i + 3 < len(s)
                and s[i + 3] != w):
            ans += c[i + 3]
 
    return ans
 
def solve_util2(s, c, x, y):
    ans = 0
    if (s[0] != x):
        ans += c[0]
    if (s[1] != y):
        ans += c[1]
    return ans
 
# Function to convert given
# string to required form
def minOperations(N, S, C):
 
    # code here
    if (len(S) == 2):
        x = solve_util2(S, C, '0', '1')
        y = solve_util2(S, C, '1', '0')
        z = solve_util2(S, C, '1', '1')
        w = solve_util2(S, C, '0', '0')
        print(f"{x},{y},{z},{w}")
        return min([x, y, z, w])
 
    x = solve_util(S, C, '0', '1', '0', '1')
    y = solve_util(S, C, '1', '0', '1', '0')
    z = solve_util(S, C, '1', '1', '0', '0')
    w = solve_util(S, C, '0', '0', '1', '1')
 
    return min([x, y, z, w])
 
# Driver Code
N = 4
s = "1011"
ct = [1, 2, 1, 3]
 
print(minOperations(N, s, ct))
 
# This code is contributed by gfgking

C#

// C# program for the above approach
using System;
class GFG
{
 
  static int solve_util(char []s, int []c,
                        char x, char y,
                        char z, char w)
  {
    int ans = 0;
    for (int i = 0; i < s.Length; i += 4) {
      if (s[i] != x)
        ans += c[i];
      if (i + 1 < s.Length
          && s[i + 1] != y)
        ans += c[i + 1];
      if (i + 2 < s.Length
          && s[i + 2] != z)
        ans += c[i + 2];
      if (i + 3 < s.Length
          && s[i + 3] != w)
        ans += c[i + 3];
    }
    return ans;
  }
 
  static int solve_util2(char []s, int []c,
                         char x, char y)
  {
    int ans = 0;
    if (s[0] != x)
      ans += c[0];
    if (s[1] != y)
      ans += c[1];
    return ans;
  }
 
  // Function to convert given
  // string to required form
  static int minOperations(int N, char []S, int []C)
  {
    // code here
    if (S.Length == 2) {
      int x = solve_util2(
        S, C, '0', '1');
      int y = solve_util2(
        S, C, '1', '0');
      int z = solve_util2(
        S, C, '1', '1');
      int w = solve_util2(
        S, C, '0', '0');
      return Math.Min(x, Math.Min( y, Math.Min(z, w )));
    }
     
    else {
      int x = solve_util(
        S, C, '0', '1', '0', '1');
      int y = solve_util(
        S, C, '1', '0', '1', '0');
      int z = solve_util(
        S, C, '1', '1', '0', '0');
      int w = solve_util(
        S, C, '0', '0', '1', '1');
      return Math.Min(x, Math.Min( y, Math.Min(z, w )));
    }
  }
 
  // Driver Code
  public static void Main () {
    int N = 4;
    char []s = {'1', '0', '1', '1'};
    int []ct = { 1, 2, 1, 3 };
 
    Console.Write(minOperations(N, s, ct));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
    // JavaScript program for above approach
 
    const solve_util = (s, c, x, y, z, w) => {
        let ans = 0;
        for (let i = 0; i < s.length; i += 4) {
            if (s[i] != x)
                ans += c[i];
            if (i + 1 < s.length
                && s[i + 1] != y)
                ans += c[i + 1];
            if (i + 2 < s.length
                && s[i + 2] != z)
                ans += c[i + 2];
            if (i + 3 < s.length
                && s[i + 3] != w)
                ans += c[i + 3];
        }
        return ans;
    }
 
    const solve_util2 = (s, c, x, y) => {
        let ans = 0;
        if (s[0] != x)
            ans += c[0];
        if (s[1] != y)
            ans += c[1];
        return ans;
    }
 
    // Function to convert given
    // string to required form
    const minOperations = (N, S, C) => {
     
        // code here
        if (S.length == 2) {
            let x = solve_util2(S, C, '0', '1');
            let y = solve_util2(S, C, '1', '0');
            let z = solve_util2(S, C, '1', '1');
            let w = solve_util2(S, C, '0', '0');
            document.write(`${x},${y},${z},${w}`);
            return Math.min(...[x, y, z, w]);
        }
        let x = solve_util(S, C, '0', '1', '0', '1');
        let y = solve_util(S, C, '1', '0', '1', '0');
        let z = solve_util(S, C, '1', '1', '0', '0');
        let w = solve_util(S, C, '0', '0', '1', '1');
 
        return Math.min(...[x, y, z, w]);
    }
 
    // Driver Code
    let N = 4;
    let s = "1011";
    let ct = [1, 2, 1, 3];
 
    document.write(minOperations(N, s, ct));
 
    // This code is contributed by rakeshsahni
 
</script>
Producción

1

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por harshalkhond 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 *