Suma mínima de medianas de todas las posibles subsecuencias de longitud K de una array ordenada

Dada una array ordenada arr[] que consta de N enteros y un entero positivo K (tal que N%K es 0 ), la tarea es encontrar la suma mínima de las medianas de todas las subsecuencias posibles de tamaño K tal que cada elemento pertenece a una única subsecuencia.

Ejemplos:

Entrada: arr[] = {1, 2, 3, 4, 5, 6}, K = 2
Salida: 6
Explicación:
considere las subsecuencias de sizeK como {1, 4}, {2, 5} y {3, 6}.
La suma de las medianas de todas las subsucesiones es (1 + 2 + 3) = 6 que es la mínima suma posible.

Entrada: K = 3, arr[] = {3, 11, 12, 22, 33, 35, 38, 67, 69, 71, 94, 99}, K = 3
Salida: 135

Enfoque ingenuo: el problema dado se puede resolver generando todas las subsecuencias ordenadas de tamaño K posibles e imprimir la mediana de todas esas subsecuencias como resultado.

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

Enfoque eficiente: el enfoque anterior también se puede optimizar utilizando el enfoque codicioso para la construcción de todas las subsecuencias. La idea es seleccionar K/2 elementos desde el inicio del arreglo y K/2 elementos desde el final del arreglo de modo que la mediana siempre ocurra en la primera parte. Siga los pasos a continuación para resolver el problema:

  • Inicializa una variable, digamos res , que almacena la suma resultante de las medianas.
  • Inicialice una variable, digamos T como N/K para almacenar el número de subsecuencias requeridas y una variable D como (K + 1)/2 para almacenar la distancia entre las medianas.
  • Inicialice una variable, digamos i como (D – 1) para almacenar el índice de la primera mediana que se agregará al resultado.
  • Iterar hasta el valor de i < N y T > 0 , y realizar los siguientes pasos:
    • Agregue el valor de arr[i] a la variable res .
    • Incremente el valor de i por D para obtener el índice de la siguiente mediana.
    • Disminuya el valor de T en 1 .
  • Después de completar los pasos anteriores, imprima el valor de res como resultado.

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 minimum sum of
// all the medians of the K sized sorted
// arrays formed from the given array
void sumOfMedians(int arr[], int N,
                  int K)
{
    // Stores the distance between
    // the medians
    int selectMedian = (K + 1) / 2;
 
    // Stores the number of subsequences
    // required
    int totalArrays = N / K;
 
    // Stores the resultant sum
    int minSum = 0;
 
    // Iterate from start and add
    // all the medians
    int i = selectMedian - 1;
    while (i < N and totalArrays != 0) {
 
        // Add the value of arr[i]
        // to the variable minsum
        minSum = minSum + arr[i];
 
        // Increment i by select the
        // median to get the next
        // median index
        i = i + selectMedian;
 
        // Decrement the value of
        // totalArrays by 1
        totalArrays--;
    }
 
    // Print the resultant minimum sum
    cout << minSum;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6 };
    int N = sizeof(arr) / sizeof(int);
    int K = 2;
    sumOfMedians(arr, N, K);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
public class GFG {
 
    // Function to find the minimum sum of
    // all the medians of the K sized sorted
    // arrays formed from the given array
    static void sumOfMedians(int arr[], int N, int K)
    {
        // Stores the distance between
        // the medians
        int selectMedian = (K + 1) / 2;
 
        // Stores the number of subsequences
        // required
        int totalArrays = N / K;
 
        // Stores the resultant sum
        int minSum = 0;
 
        // Iterate from start and add
        // all the medians
        int i = selectMedian - 1;
        while (i < N && totalArrays != 0) {
 
            // Add the value of arr[i]
            // to the variable minsum
            minSum = minSum + arr[i];
 
            // Increment i by select the
            // median to get the next
            // median index
            i = i + selectMedian;
 
            // Decrement the value of
            // totalArrays by 1
            totalArrays--;
        }
 
        // Print the resultant minimum sum
        System.out.println(minSum);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 3, 4, 5, 6 };
        int N = arr.length;
        int K = 2;
        sumOfMedians(arr, N, K);
    }
}
 
// This code is contributed by Kingash.

Python3

# Python3 program for the above approach
 
# Function to find the minimum sum of
# all the medians of the K sized sorted
# arrays formed from the given array
def sumOfMedians(arr, N, K):
 
    # Stores the distance between
    # the medians
    selectMedian = (K + 1) // 2
 
    # Stores the number of subsequences
    # required
    totalArrays = N // K
 
    # Stores the resultant sum
    minSum = 0
 
    # Iterate from start and add
    # all the medians
    i = selectMedian - 1
     
    while (i < N and totalArrays != 0):
 
        # Add the value of arr[i]
        # to the variable minsum
        minSum = minSum + arr[i]
 
        # Increment i by select the
        # median to get the next
        # median index
        i = i + selectMedian
 
        # Decrement the value of
        # totalArrays by 1
        totalArrays -= 1
 
     # Print the resultant minimum sum
    print(minSum)
 
 # Driver Code
if __name__ == '__main__':
     
    arr = [ 1, 2, 3, 4, 5, 6 ]
    N = len(arr)
    K = 2
     
    sumOfMedians(arr, N, K)
 
# This code is contributed by nirajgsuain5

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
  
class GFG{
  
    // Function to find the minimum sum of
    // all the medians of the K sized sorted
    // arrays formed from the given array
    static void sumOfMedians(int[] arr, int N, int K)
    {
       
        // Stores the distance between
        // the medians
        int selectMedian = (K + 1) / 2;
  
        // Stores the number of subsequences
        // required
        int totalArrays = N / K;
  
        // Stores the resultant sum
        int minSum = 0;
  
        // Iterate from start and add
        // all the medians
        int i = selectMedian - 1;
        while (i < N && totalArrays != 0) {
  
            // Add the value of arr[i]
            // to the variable minsum
            minSum = minSum + arr[i];
  
            // Increment i by select the
            // median to get the next
            // median index
            i = i + selectMedian;
  
            // Decrement the value of
            // totalArrays by 1
            totalArrays--;
        }
  
        // Print the resultant minimum sum
        Console.WriteLine(minSum);
    }
  
// Driver Code
public static void Main()
{
        int[] arr = { 1, 2, 3, 4, 5, 6 };
        int N = arr.Length;
        int K = 2;
        sumOfMedians(arr, N, K);
      
}
}
 
// This code is contributed by code_hunt.

Javascript

<script>
 
// JavaScript program for the above approach
 
    // Function to find the minimum sum of
    // all the medians of the K sized sorted
    // arrays formed from the given array
    function sumOfMedians(arr, N, K)
    {
        // Stores the distance between
        // the medians
        let selectMedian = Math.floor((K + 1) / 2);
  
        // Stores the number of subsequences
        // required
        let totalArrays =  Math.floor(N / K);
  
        // Stores the resultant sum
        let minSum = 0;
  
        // Iterate from start and add
        // all the medians
        let i = selectMedian - 1;
        while (i < N && totalArrays != 0) {
  
            // Add the value of arr[i]
            // to the variable minsum
            minSum = minSum + arr[i];
  
            // Increment i by select the
            // median to get the next
            // median index
            i = i + selectMedian;
  
            // Decrement the value of
            // totalArrays by 1
            totalArrays--;
        }
  
        // Print the resultant minimum sum
       document.write(minSum);
    }
 
 
// Driver Code
 
        let arr = [ 1, 2, 3, 4, 5, 6 ];
        let N = arr.length;
        let K = 2;
        sumOfMedians(arr, N, K);   
 
</script>
Producción: 

6

 

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

Publicación traducida automáticamente

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