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>
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