Dada una array ordenada arr[] de N enteros y un entero K , la tarea es dividir la array en K subarreglos de manera que la suma de la diferencia del elemento máximo y mínimo de cada subarreglo se minimice.
Ejemplos:
Entrada: arr[] = {1, 3, 3, 7}, K = 4
Salida: 0
Explicación:
La array dada se puede dividir en 4 subarreglos como {1}, {3}, {3} y {7} .
La diferencia entre el mínimo y el máximo de cada subarreglo es:
1. {1}, diferencia = 1 – 1 = 0
2. {3}, diferencia = 3 – 3 = 0
3. {3}, diferencia = 3 – 3 = 0
4. {7}, diferencia = 7 – 7 = 0
Por lo tanto, la suma de todas las diferencias es 0, que se minimiza.Entrada: arr[] = {4, 8, 15, 16, 23, 42}, K = 3
Salida: 12
Explicación:
La array dada se puede dividir en 3 subarreglos como {4, 8, 15, 16}, {23 } y {42}.
La diferencia entre el mínimo y el máximo de cada subarreglo es:
1. {4, 8, 15, 16}, diferencia = 16 – 4 = 12
2. {23}, diferencia = 23 – 23 = 0
3. {42}, diferencia = 42 – 42 = 0
Por lo tanto, la suma de toda la diferencia es 12 que se minimiza.
Enfoque: para dividir la array dada en K subarreglos con las condiciones dadas, la idea es dividir en índices (por ejemplo, i ) donde la diferencia entre los elementos arr[i+1] y arr[i] es mayor. A continuación se detallan los pasos para implementar este enfoque:
- Almacene la diferencia entre pares consecutivos de elementos en la array dada arr[] en otra array (digamos temp[] ).
- Ordene la array temp[] en orden creciente.
- Inicialice la diferencia total (digamos diff ) como la diferencia del primer y último elemento de la array dada arr[] .
- Agregue los primeros valores K – 1 de la array temp[] a la diferencia anterior.
- El valor almacenado en diff es la suma mínima de la diferencia del elemento máximo y mínimo del subarreglo K.
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 subarray int find(int a[], int n, int k) { vector<int> v; // Add the difference to vectors for (int i = 1; i < n; ++i) { v.push_back(a[i - 1] - a[i]); } // Sort vector to find minimum k sort(v.begin(), v.end()); // Initialize result int res = a[n - 1] - a[0]; // Adding first k-1 values for (int i = 0; i < k - 1; ++i) { res += v[i]; } // Return the minimized sum return res; } // Driver Code int main() { // Given array arr[] int arr[] = { 4, 8, 15, 16, 23, 42 }; int N = sizeof(arr) / sizeof(int); // Given K int K = 3; // Function Call cout << find(arr, N, K) << endl; return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the subarray static int find(int a[], int n, int k) { Vector<Integer> v = new Vector<Integer>(); // Add the difference to vectors for(int i = 1; i < n; ++i) { v.add(a[i - 1] - a[i]); } // Sort vector to find minimum k Collections.sort(v); // Initialize result int res = a[n - 1] - a[0]; // Adding first k-1 values for(int i = 0; i < k - 1; ++i) { res += v.get(i); } // Return the minimized sum return res; } // Driver Code public static void main(String[] args) { // Given array arr[] int arr[] = { 4, 8, 15, 16, 23, 42 }; int N = arr.length; // Given K int K = 3; // Function Call System.out.print(find(arr, N, K) + "\n"); } } // This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach # Function to find the subarray def find(a, n, k): v = [] # Add the difference to vectors for i in range(1, n): v.append(a[i - 1] - a[i]) # Sort vector to find minimum k v.sort() # Initialize result res = a[n - 1] - a[0] # Adding first k-1 values for i in range(k - 1): res += v[i] # Return the minimized sum return res # Driver code arr = [ 4, 8, 15, 16, 23, 42 ] # Length of array N = len(arr) K = 3 # Function Call print(find(arr, N, K)) # This code is contributed by sanjoy_62
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to find the subarray static int find(int []a, int n, int k) { List<int> v = new List<int>(); // Add the difference to vectors for(int i = 1; i < n; ++i) { v.Add(a[i - 1] - a[i]); } // Sort vector to find minimum k v.Sort(); // Initialize result int res = a[n - 1] - a[0]; // Adding first k-1 values for(int i = 0; i < k - 1; ++i) { res += v[i]; } // Return the minimized sum return res; } // Driver Code public static void Main(String[] args) { // Given array []arr int []arr = { 4, 8, 15, 16, 23, 42 }; int N = arr.Length; // Given K int K = 3; // Function Call Console.Write(find(arr, N, K) + "\n"); } } // This code is contributed by Amit Katiyar
Javascript
<script> // javascript program for the above approach // Function to find the subarray function find(a , n , k) { var v = []; // Add the difference to vectors for (i = 1; i < n; ++i) { v.push(a[i - 1] - a[i]); } // Sort vector to find minimum k v.sort((a,b)=>a-b); // Initialize result var res = a[n - 1] - a[0]; // Adding first k-1 values for (i = 0; i < k - 1; ++i) { res += v[i]; } // Return the minimized sum return res; } // Driver Code // Given array arr var arr = [ 4, 8, 15, 16, 23, 42 ]; var N = arr.length; // Given K var K = 3; // Function Call document.write(find(arr, N, K) + "\n"); // This code contributed by aashish1995 </script>
12
Complejidad de tiempo: O(N) , donde N es el número de elementos en la array.
Espacio auxiliar: O(N) , donde N es el número de elementos del arreglo.
Publicación traducida automáticamente
Artículo escrito por chitrasingla2001 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA