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