Dada una array A[] de tamaño N y un entero positivo K (que siempre será un factor de N ), la tarea es encontrar la suma máxima posible de los segundos elementos más pequeños de cada partición de la array dividiendo la array en (N/K) particiones de igual tamaño.
Ejemplos:
Entrada: A[] = {2, 3, 1, 4, 7, 5, 6, 1}, K = 4
Salida: 7
Explicación: Divida la array como {1, 2, 3, 4} y {1, 5 , 6, 7}. Por tanto, suma = 2 + 5 = 7, que es la máxima suma posible.Entrada: A[] = {12, 43, 15, 32, 45, 23}, K = 3
Salida: 66
Explicación: Divida la array como {12, 23, 32} y {15, 43, 45}. Por lo tanto, suma = 23 + 43 = 66, que es la suma máxima posible.
Enfoque: La idea es ordenar la array dada en orden ascendente y para maximizar la suma requerida, dividir los primeros N / K elementos de A[] en cada una de las arrays como su primer término, luego elegir cada (K – 1 ) el elemento de A[] a partir de N/K .
Siga los pasos a continuación para resolver el problema:
- Ordene la array A[] en orden creciente.
- Inicialice la suma con 0 para almacenar la suma requerida.
- Ahora, inicialice una variable i con N / K .
- Mientras i es menor que N , realice los siguientes pasos:
- Incrementar suma por A[i] .
- Incremente i por K – 1 .
- Después de atravesar, imprima la suma como la respuesta requerida.
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 maximum sum of // second smallest of each partition // of size K void findSum(int A[], int N, int K) { // Sort the array A[] // in ascending order sort(A, A + N); // Store the maximum sum of second // smallest of each partition // of size K int sum = 0; // Select every (K-1)th element as // second smallest element for (int i = N / K; i < N; i += K - 1) { // Update sum sum += A[i]; } // Print the maximum sum cout << sum; } // Driver Code int main() { // Given size of partitions int K = 4; // Given array A[] int A[] = { 2, 3, 1, 4, 7, 5, 6, 1 }; // Size of the given array int N = sizeof(A) / sizeof(A[0]); // Function Call findSum(A, N, K); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the maximum sum of // second smallest of each partition // of size K static void findSum(int A[], int N, int K) { // Sort the array A[] // in ascending order Arrays.sort(A); // Store the maximum sum of second // smallest of each partition // of size K int sum = 0; // Select every (K-1)th element as // second smallest element for(int i = N / K; i < N; i += K - 1) { // Update sum sum += A[i]; } // Print the maximum sum System.out.print(sum); } // Driver Code public static void main(String[] args) { // Given size of partitions int K = 4; // Given array A[] int A[] = { 2, 3, 1, 4, 7, 5, 6, 1 }; // Size of the given array int N = A.length; // Function Call findSum(A, N, K); } } // This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach # Function to find the maximum sum of # second smallest of each partition # of size K def findSum(A, N, K): # Sort the array A # in ascending order A.sort(); # Store the maximum sum of second # smallest of each partition # of size K sum = 0; # Select every (K-1)th element as # second smallest element for i in range(N // K, N, K - 1): # Update sum sum += A[i]; # Print the maximum sum print(sum); # Driver Code if __name__ == '__main__': # Given size of partitions K = 4; # Given array A A = [2, 3, 1, 4, 7, 5, 6, 1]; # Size of the given array N = len(A); # Function Call findSum(A, N, K); # This code contributed by shikhasingrajput
C#
// C# program for the above approach using System; class GFG{ // Function to find the maximum sum of // second smallest of each partition // of size K static void findSum(int []A, int N, int K) { // Sort the array []A // in ascending order Array.Sort(A); // Store the maximum sum of second // smallest of each partition // of size K int sum = 0; // Select every (K-1)th element as // second smallest element for(int i = N / K; i < N; i += K - 1) { // Update sum sum += A[i]; } // Print the maximum sum Console.Write(sum); } // Driver Code public static void Main(String[] args) { // Given size of partitions int K = 4; // Given array []A int []A = { 2, 3, 1, 4, 7, 5, 6, 1 }; // Size of the given array int N = A.Length; // Function Call findSum(A, N, K); } } // This code is contributed by shikhasingrajput
Javascript
<script> // Javascript program of the above approach // Function to find the maximum sum of // second smallest of each partition // of size K function findSum(A, N, K) { // Sort the array A[] // in ascending order A.sort(); // Store the maximum sum of second // smallest of each partition // of size K let sum = 0; // Select every (K-1)th element as // second smallest element for(let i = N / K; i < N; i += K - 1) { // Update sum sum += A[i]; } // Print the maximum sum document.write(sum); } // Driver Code // Given size of partitions let K = 4; // Given array A[] let A = [ 2, 3, 1, 4, 7, 5, 6, 1 ]; // Size of the given array let N = A.length; // Function Call findSum(A, N, K); // This code is contributed by chinmoy1997pal </script>
7
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA