Costo mínimo para convertir todos los elementos de un subarreglo de tamaño K a 0 desde un Ternary Array dado con la suma del subarreglo como costo

Posted on by Rudeus Greyrat

Dada una array arr[] de N enteros, donde cada elemento de la array es 0, 1 o 2 , y un entero K , la tarea es imprimir el costo mínimo necesario para convertir todos los elementos de la array a 0 s seleccionando un subarreglo de tamaño K y convertir cualquier elemento del arreglo del subarreglo a 0 en una operación con el costo igual a la suma de los elementos del subarreglo.

Ejemplos:

Entrada: arr[] = {2, 0, 1, 1, 0, 2}, K = 3
Salida: 3
Explicación: 
Realice los siguientes pasos:

  1. Seleccione el subarreglo sobre el rango [1, 3] y luego cambie el arr[2](= 1) a 0 a un costo de 2. El arreglo se modifica a arr[] = {2, 0, 0, 1, 0 , 2}.
  2. Seleccione el subarreglo sobre el rango [1, 3] y luego cambie el arr[3](= 1) a 0 a un costo de 1. El arreglo se modifica a arr[] = {2, 0, 0, 0, 0 , 2}.
  3. Seleccione el subarreglo sobre el rango [0, 2] y luego cambie el arr[0](= 2) a 0 a un costo de 2. El arreglo se modifica a arr[] = {0, 0, 0, 0, 0 , 2}.
  4. Seleccione el subarreglo sobre el rango [3, 5] y luego cambie el arr[5](= 2) a 0 a un costo de 2. El arreglo se modifica a arr[] = {0, 0, 0, 0, 0 , 0}.

Por lo tanto, el costo total necesario es (2+1+2+2 = 7). Y también es el costo mínimo necesario.

Entrada: arr[] = {1, 0, 2, 1}, K = 4
Salida: 7

Enfoque: El problema dado se puede resolver con base en las siguientes observaciones: 

  1. Es óptimo convertir primero todos los elementos del subarreglo de tamaño K que tienen el costo mínimo y el número máximo de 2 s a 0 .
  2. Supongamos que X es la cuenta de 1 s e Y es la cuenta de 2 s en el subarreglo con costo mínimo. Luego, convertir todos los 2 s a 0 primero y luego todos los 1 s a 0 darán el costo mínimo para convertir el subarreglo a 0 .
  3. El costo de convertir los 2 s a 0 es:
    • (X+2*Y)+(X+2*Y-2) +(X+2*Y-4)+ … +(X+2*Y-2*(Y-1)) 
      = Y*(X +2*Y) – Y*(0+2*(Y-1))/2 
      = Y*(X+2*Y) – Y*(Y-1)
      = X*Y+2*Y 2 -Y 2 +Y = Y 2 + X*Y + Y 
  4. El costo de convertir todos los 1 s restantes a 0 es:
    • X+ (X-1)+(X-2)+ … + 1
      = (X*(X+1))/2
  5. Por lo tanto, el costo de convertir todos los elementos de un subarreglo con X 1 s e Y 2 s es igual a:
    •  Y2 + X*Y+Y+(X*(X+1))/2
  6. Ahora, los elementos restantes se pueden convertir a 0 s tomando un subarreglo con K-1 0 s y el elemento, que tendrá un costo igual al elemento mismo.
  7. Por lo tanto, si la suma es la suma total de la array, entonces, el costo mínimo será igual a:
    • suma-(X+2*Y) + Y 2 +X*Y+Y+(X*(X+1))/2

Siga los pasos a continuación para resolver el problema:

  • Inicialice dos arrays , digamos pcount1[] y pcount2[] como {0} donde pcount1[i] y pcount2[i] almacenan la cuenta de 1 s y 2 s en el prefijo sobre el rango [0, i].
  • Recorra la array, arr[] usando la variable i y haga lo siguiente:
    • Asigne pcount1[i] a pcount1[i+1] y pcount2[i] a pcount2[i+1] .
    • Si arr[i] es 1 , entonces incremente pcount1[i+1] . De lo contrario, si arr[i] es 2 , entonces el recuento de incrementos de pcount2[i+1] .
  • Encuentre la suma de la array y guárdela en una variable, digamos suma.
  • Inicialice dos variables, digamos X e Y , para almacenar el conteo de 1 s y 2 s en el subarreglo con una suma mínima de tamaño K .
  • Iterar sobre el rango [K, N] usando la variable i y realizar los siguientes pasos:
    • Inicialice dos variables, digamos A y B , para almacenar el conteo de 1 s y 2 s en el subarreglo sobre el rango [iK, K-1].
    • Asigne pcount1[i]-pcount1[iK] a A y pcount2[i]-pcount2[iK] a B .
    • Si A+2*B es menor que X+2*Y , actualice X a A e Y a B .
  • Finalmente, después de completar los pasos anteriores, imprima el costo total como sum-(X+2*Y) + Y 2 +X*Y+Y+(X*(X+1))/2.

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the min cost
int minCost(int arr[], int N, int K)
{
    // Stores the prefix count of 1s
    int pcount1[N + 1] = { 0 };
    // Stores the prefix count of 2s
    int pcount2[N + 1] = { 0 };
 
    // Traverse the array arr[]
    for (int i = 1; i <= N; i++) {
        pcount1[i] = pcount1[i - 1] + (arr[i - 1] == 1);
        pcount2[i] = pcount2[i - 1] + (arr[i - 1] == 2);
    }
 
    // Stores total sum of the array arr[]
    int sum = pcount1[N] + 2 * pcount2[N];
 
    // Stores the count of 1s in a subarray
    int X = N;
 
    // Stores the count of 2s in a subarray
    int Y = N;
 
    // Iterate over the range [K, N]
    for (int i = K; i <= N; i++) {
        int A = pcount1[i] - pcount1[i - K];
        int B = pcount2[i] - pcount2[i - K];
 
        // If current subarray sum is less
        // than X+2*Y
        if (A + 2 * B < X + 2 * Y) {
            X = A;
            Y = B;
        }
    }
 
    // Stores the total cost
    int total = sum - (X + 2 * Y) + Y * Y + X * Y + Y
                + (X * (X + 1)) / 2;
    // Return total
    return total;
}
 
// Driver Code
int main()
{
 
    // Input
    int arr[] = { 2, 0, 1, 1, 0, 2 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 3;
    // Function call
    cout << minCost(arr, N, K);
 
    return 0;
}

Java

// Java Program for the above approach
import java.io.*;
import java.util.Arrays;
class GFG
{
   
    // Function to find the min cost
    static int minCost(int arr[], int N, int K)
    {
       
        // Stores the prefix count of 1s
        int pcount1[] = new int[N + 1];
       
        // Stores the prefix count of 2s
        int pcount2[] = new int[N + 1];
        Arrays.fill(pcount1, 0);
        Arrays.fill(pcount2, 0);
 
        // Traverse the array arr[]
        for (int i = 1; i <= N; i++) {
            int k = 0;
            int l = 0;
            if (arr[i - 1] == 1)
                k = 1;
 
            if (arr[i - 1] == 2)
                l = 1;
 
            pcount1[i] = pcount1[i - 1] + k;
            pcount2[i] = pcount2[i - 1] + l;
        }
 
        // Stores total sum of the array arr[]
        int sum = pcount1[N] + 2 * pcount2[N];
 
        // Stores the count of 1s in a subarray
        int X = N;
 
        // Stores the count of 2s in a subarray
        int Y = N;
 
        // Iterate over the range [K, N]
        for (int i = K; i <= N; i++) {
            int A = pcount1[i] - pcount1[i - K];
            int B = pcount2[i] - pcount2[i - K];
 
            // If current subarray sum is less
            // than X+2*Y
            if (A + 2 * B < X + 2 * Y) {
                X = A;
                Y = B;
            }
        }
 
        // Stores the total cost
        int total = sum - (X + 2 * Y) + Y * Y + X * Y + Y
                    + (X * (X + 1)) / 2;
        // Return total
        return total;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
       
        // Input
        int arr[] = { 2, 0, 1, 1, 0, 2 };
        int N = arr.length;
        int K = 3;
        // Function call
 
        System.out.println(minCost(arr, N, K));
 
    }
}
 
      // This code is contributed by Potta Lokesh

Python3

# Py program for the above approach
 
# Function to find the min cost
def minCost(arr, N, K):
   
    # Stores the prefix count of 1s
    pcount1 = [0] * (N + 1)
     
    # Stores the prefix count of 2s
    pcount2 = [0] * (N+1)
     
    # Traverse the array arr[]
    for i in range(1,N+1):
        pcount1[i] = pcount1[i - 1] + (arr[i - 1] == 1)
        pcount2[i] = pcount2[i - 1] + (arr[i - 1] == 2)
 
    # Stores total sum of the array arr[]
    sum = pcount1[N] + 2 * pcount2[N]
 
    # Stores the count of 1s in a subarray
    X = N
 
    # Stores the count of 2s in a subarray
    Y = N
 
    # Iterate over the range [K, N]
    for i in range(K, N + 1):
        A = pcount1[i] - pcount1[i - K]
        B = pcount2[i] - pcount2[i - K]
 
        # If current subarray sum is less
        # than X+2*Y
        if (A + 2 * B < X + 2 * Y):
            X = A
            Y = B
 
    # Stores the total cost
    total = sum - (X + 2 * Y) + Y * Y + X * Y + Y + (X * (X + 1)) // 2
    # Return total
    return total
 
# Driver Code
if __name__ == '__main__':
   
    # Input
    arr= [2, 0, 1, 1, 0, 2]
    N =  len(arr)
    K = 3
     
    # Function call
    print (minCost(arr, N, K))
 
# This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the min cost
static int minCost(int []arr, int N, int K)
{
    // Stores the prefix count of 1s
    int []pcount1 = new int[N + 1];
    Array.Clear(pcount1, 0, N + 1);
   
    // Stores the prefix count of 2s
    int []pcount2 = new int[N + 1];
    Array.Clear(pcount2, 0, N + 1);
 
    // Traverse the array arr[]
    for (int i = 1; i <= N; i++) {
        if(arr[i - 1] == 1){
          pcount1[i] = pcount1[i - 1] + 1;
        }
        else
          pcount1[i] = pcount1[i - 1];
           
         if(arr[i - 1] == 2){
          pcount2[i] = pcount2[i - 1] + 1;
        }
        else
          pcount2[i] = pcount2[i - 1];
        
    }
 
    // Stores total sum of the array arr[]
    int sum = pcount1[N] + 2 * pcount2[N];
 
    // Stores the count of 1s in a subarray
    int X = N;
 
    // Stores the count of 2s in a subarray
    int Y = N;
 
    // Iterate over the range [K, N]
    for (int i = K; i <= N; i++) {
        int A = pcount1[i] - pcount1[i - K];
        int B = pcount2[i] - pcount2[i - K];
 
        // If current subarray sum is less
        // than X+2*Y
        if (A + 2 * B < X + 2 * Y) {
            X = A;
            Y = B;
        }
    }
 
    // Stores the total cost
    int total = sum - (X + 2 * Y) + Y * Y + X * Y + Y
                + (X * (X + 1)) / 2;
    // Return total
    return total;
}
 
// Driver Code
public static void Main()
{
 
    // Input
    int []arr = { 2, 0, 1, 1, 0, 2 };
    int N = arr.Length;
    int K = 3;
   
    // Function call
    Console.Write(minCost(arr, N, K));
}
}
 
// This code is contributed by SURENDRA_GANGWAR.

Javascript

// Javascript program for the above approach
 
// Function to find the min cost
function minCost(arr, N, K)
{
 
    // Stores the prefix count of 1s
    let pcount1 = new Array(N + 1).fill(0);
     
    // Stores the prefix count of 2s
    let pcount2 = new Array(N + 1).fill(0);
 
    // Traverse the array arr[]
    for (let i = 1; i <= N; i++) {
        pcount1[i] = pcount1[i - 1] + (arr[i - 1] == 1);
        pcount2[i] = pcount2[i - 1] + (arr[i - 1] == 2);
    }
 
    // Stores total sum of the array arr[]
    let sum = pcount1[N] + 2 * pcount2[N];
 
    // Stores the count of 1s in a subarray
    let X = N;
 
    // Stores the count of 2s in a subarray
    let Y = N;
 
    // Iterate over the range [K, N]
    for (let i = K; i <= N; i++) {
        let A = pcount1[i] - pcount1[i - K];
        let B = pcount2[i] - pcount2[i - K];
 
        // If current subarray sum is less
        // than X+2*Y
        if (A + 2 * B < X + 2 * Y) {
            X = A;
            Y = B;
        }
    }
 
    // Stores the total cost
    let total = sum - (X + 2 * Y) + Y * Y + X * Y + Y
        + (X * (X + 1)) / 2;
         
    // Return total
    return total;
}
 
// Driver Code
 
// Input
let arr = [2, 0, 1, 1, 0, 2];
let N = arr.length;
let K = 3;
 
// Function call
document.write(minCost(arr, N, K));
 
// This code is contributed by gfgking.
Producción

7

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

Publicación traducida automáticamente

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