Dadas dos arrays arr[] y S[] que consisten en N y K enteros, la tarea es encontrar la suma máxima del mínimo y el máximo de cada subconjunto después de dividir la array en K subconjuntos de modo que el tamaño de cada subconjunto sea igual a uno de los elementos de la array S[] .
Ejemplos:
Entrada: arr[] = {1, 13, 7, 17}, S[] = {1, 3}
Salida: 48
Explicación: considere dividir la array como {17}, {1, 7, 13}, de modo que el tamaño de los subconjuntos son 1 y 3 respectivamente, que está presente en la array S[].
La suma del máximo y mínimo de cada subconjunto es (17 + 17 + 1 + 13) = 48.Entrada: arr[ ] = {5, 1, -30, 0, 11, 20, 19}, S[] = {4, 1, 2}
Salida: 45
Enfoque: El problema dado se puede resolver usando el Enfoque codicioso , la idea es insertar los primeros K elementos máximos en cada grupo y luego comenzar a llenar los grupos de menor tamaño primero con elementos más grandes. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans como 0 , para almacenar la suma del máximo y el mínimo de todos los subconjuntos.
- Ordene la array arr[] en orden descendente .
- Ordene la array S[] en orden ascendente.
- Encuentre la suma de los primeros K elementos de la array y guárdela en la variable ans , y disminuya todos los elementos de S[] en 1 .
- Inicialice una variable, digamos contador como K – 1 , para almacenar el índice del elemento mínimo de cada subconjunto.
- Recorra la array S[] e incremente el contador en S[i] y agregue el valor de arr[contador] a ans .
- Después de completar los pasos anteriores, imprima los valores de ans 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 find maximum sum of // minimum and maximum of K subsets int maximumSum(int arr[], int S[], int N, int K) { // Stores the result int ans = 0; // Sort the array arr[] in // decreasing order sort(arr, arr + N, greater<int>()); // Traverse the range [0, K] for (int i = 0; i < K; i++) ans += arr[i]; // Sort the array S[] in // ascending order sort(S, S + K); // Traverse the array S[] for (int i = 0; i < K; i++) { // If S{i] is 1 if (S[i] == 1) ans += arr[i]; S[i]--; } // Stores the index of the minimum // element of the i-th subset int counter = K - 1; // Traverse the array S[] for (int i = 0; i < K; i++) { // Update the counter counter = counter + S[i]; if (S[i] != 0) ans += arr[counter]; } // Return the resultant sum return ans; } // Driver Code int main() { int arr[] = { 1, 13, 7, 17 }; int S[] = { 1, 3 }; int N = sizeof(arr) / sizeof(arr[0]); int K = sizeof(S) / sizeof(S[0]); cout << maximumSum(arr, S, N, K); return 0; }
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG{ // Function find maximum sum of // minimum and maximum of K subsets static int maximumSum(int arr[], int S[], int N, int K) { // Stores the result int ans = 0; // Sort the array arr[] in // decreasing order Arrays.sort(arr); for(int i = 0; i < N / 2; i++) { int temp = arr[i]; arr[i] = arr[N - 1 - i]; arr[N - 1 - i] = temp; } // Traverse the range [0, K] for(int i = 0; i < K; i++) ans += arr[i]; // Sort the array S[] in // ascending order Arrays.sort(S); // Traverse the array S[] for(int i = 0; i < K; i++) { // If S{i] is 1 if (S[i] == 1) ans += arr[i]; S[i]--; } // Stores the index of the minimum // element of the i-th subset int counter = K - 1; // Traverse the array S[] for(int i = 0; i < K; i++) { // Update the counter counter = counter + S[i]; if (S[i] != 0) ans += arr[counter]; } // Return the resultant sum return ans; } // Driver Code public static void main(String[] args) { int arr[] = { 1, 13, 7, 17 }; int S[] = { 1, 3 }; int N = arr.length; int K = S.length; System.out.println(maximumSum(arr, S, N, K)); } } // This code is contributed by Kingash
Python3
# Python3 program for the above approach # Function find maximum sum of # minimum and maximum of K subsets def maximumSum(arr, S, N, K): # Stores the result ans = 0 # Sort the array arr[] in # decreasing order arr = sorted(arr)[::-1] # Traverse the range [0, K] for i in range(K): ans += arr[i] # Sort the array S[] in # ascending order S = sorted(S) # Traverse the array S[] for i in range(K): # If S{i] is 1 if (S[i] == 1): ans += arr[i] S[i] -= 1 # Stores the index of the minimum # element of the i-th subset counter = K - 1 # Traverse the array S[] for i in range(K): # Update the counter counter = counter + S[i] if (S[i] != 0): ans += arr[counter] # Return the resultant sum return ans # Driver Code if __name__ == '__main__': arr = [ 1, 13, 7, 17 ] S = [ 1, 3 ] N = len(arr) K = len(S) print (maximumSum(arr, S, N, K)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach using System; class GFG { // Function find maximum sum of // minimum and maximum of K subsets static int maximumSum(int[] arr, int[] S, int N, int K) { // Stores the result int ans = 0; // Sort the array arr[] in // decreasing order Array.Sort(arr); for (int i = 0; i < N / 2; i++) { int temp = arr[i]; arr[i] = arr[N - 1 - i]; arr[N - 1 - i] = temp; } // Traverse the range [0, K] for (int i = 0; i < K; i++) ans += arr[i]; // Sort the array S[] in // ascending order Array.Sort(S); // Traverse the array S[] for (int i = 0; i < K; i++) { // If S{i] is 1 if (S[i] == 1) ans += arr[i]; S[i]--; } // Stores the index of the minimum // element of the i-th subset int counter = K - 1; // Traverse the array S[] for (int i = 0; i < K; i++) { // Update the counter counter = counter + S[i]; if (S[i] != 0) ans += arr[counter]; } // Return the resultant sum return ans; } // Driver Code public static void Main(string[] args) { int[] arr = { 1, 13, 7, 17 }; int[] S = { 1, 3 }; int N = arr.Length; int K = S.Length; Console.WriteLine(maximumSum(arr, S, N, K)); } } // This code is contributed by ukasp.
Javascript
<script> // JavaScript program for the above approach // Function find maximum sum of // minimum and maximum of K subsets function maximumSum(arr, S, N, K) { // Stores the result var ans = 0; var i; // Sort the array arr[] in // decreasing order arr.sort((a, b) => b - a); // Traverse the range [0, K] for (i = 0; i < K; i++) ans += arr[i]; // Sort the array S[] in // ascending order S.sort(); // S.reverse(); // Traverse the array S[] for (i = 0; i < K; i++) { // If S{i] is 1 if (S[i] == 1) ans += arr[i]; S[i] -= 1; } // Stores the index of the minimum // element of the i-th subset var counter = K - 1; // Traverse the array S[] for (i = 0; i < K; i++) { // Update the counter counter = counter + S[i]; if (S[i] != 0) ans += arr[counter]; } // Return the resultant sum return ans; } // Driver Code var arr = [1, 13, 7, 17]; var S = [1, 3]; var N = arr.length; var K = S.length; document.write(maximumSum(arr, S, N, K)); </script>
48
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ashutoshtiwari22111998 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA