Dada una array, arr[] de tamaño N y un número entero K , la tarea es dividir la array en K subarreglos minimizando la suma de la diferencia absoluta entre los elementos adyacentes de cada subarreglo.
Ejemplos:
Entrada: arr[] = {1, 3, -2, 5, -1}, K = 2
Salida: 13
Explicación: Divida la array en las siguientes 2 subarreglas: {1, 3, -2} y {5, -1 }.Entrada: arr[] = {2, 14, 26, 10, 5, 12}, K = 3
Salida: 24
Explicación: dividir la array en los siguientes 3 subarreglos: {2, 14}, {26}, {10, 5, 12}.
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
La idea es dividir la array arr[] en el i -ésimo índice, lo que da la máxima diferencia absoluta de elementos adyacentes. Restarlo del resultado. Cortar en K – 1 lugares dará K subarreglos con la suma mínima de la diferencia absoluta de los elementos adyacentes.
Siga los pasos a continuación para resolver el problema:
- Inicialice una array, digamos new_Arr[] , y una variable entera, digamos ans , para almacenar la suma de la diferencia absoluta total.
- Atraviesa la array .
- Almacene la diferencia absoluta de los elementos adyacentes, digamos arr[i+1] y arr[i] en la array new_Arr[] .
- Incremento ans por diferencia absoluta de arr[i] y arr[i + 1]
- Ordene la array new_Arr[] en orden descendente .
- Atraviesa la array desde i = 0 hasta i = K-1
- Decrementar ans por new_Arr[i].
- Finalmente, imprima ans.
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 split an array into K subarrays
// with minimum sum of absolute difference
// of adjacent elements in each of K subarrays
void absoluteDifference(int arr[], int N, int K)
{
// Stores the absolute differences
// of adjacent elements
int new_Arr[N - 1];
// Stores the answer
int ans = 0;
// Stores absolute differences of
// adjacent elements in new_Arr
for (int i = 0; i < N - 1; i++) {
new_Arr[i] = abs(arr[i] - arr[i + 1]);
// Stores the sum of all absolute
// differences of adjacent elements
ans += new_Arr[i];
}
// Sorting the new_Arr
// in decreasing order
sort(new_Arr, new_Arr + N - 1,
greater<int>());
for (int i = 0; i < K - 1; i++) {
// Removing K - 1 elements
// with maximum sum
ans -= new_Arr[i];
}
// Prints the answer
cout << ans << endl;
}
// Driver code
int main()
{
// Given array arr[]
int arr[] = { 1, 3, -2, 5, -1 };
// Given K
int K = 2;
// Size of array
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
absoluteDifference(arr, N, K);
return 0;
}
Java
// java program for the above approach
import java.util.*;
import java.util.Arrays;
class GFG
{
public static void reverse(int[] array)
{
// Length of the array
int n = array.length;
// Swaping the first half elements with last half
// elements
for (int i = 0; i < n / 2; i++)
{
// Storing the first half elements temporarily
int temp = array[i];
// Assigning the first half to the last half
array[i] = array[n - i - 1];
// Assigning the last half to the first half
array[n - i - 1] = temp;
}
}
// Function to split an array into K subarrays
// with minimum sum of absolute difference
// of adjacent elements in each of K subarrays
public static void absoluteDifference(int arr[],
int N, int K)
{
// Stores the absolute differences
// of adjacent elements
int new_Arr[] = new int[N - 1];
// Stores the answer
int ans = 0;
// Stores absolute differences of
// adjacent elements in new_Arr
for (int i = 0; i < N - 1; i++)
{
new_Arr[i] = Math.abs(arr[i] - arr[i + 1]);
// Stores the sum of all absolute
// differences of adjacent elements
ans += new_Arr[i];
}
// Sorting the new_Arr
// in decreasing order
Arrays.sort(new_Arr);
reverse(new_Arr);
for (int i = 0; i < K - 1; i++)
{
// Removing K - 1 elements
// with maximum sum
ans -= new_Arr[i];
}
// Prints the answer
System.out.println(ans);
}
// Driver code
public static void main (String[] args)
{
// Given array arr[]
int arr[] = { 1, 3, -2, 5, -1 };
// Given K
int K = 2;
// Size of array
int N = arr.length;
// Function Call
absoluteDifference(arr, N, K);
}
}
// This code is contributed by AnkThon
Python3
# Python3 program for the above approach # Function to split an array into K subarrays # with minimum sum of absolute difference # of adjacent elements in each of K subarrays def absoluteDifference(arr, N, K): # Stores the absolute differences # of adjacent elements new_Arr = [0 for i in range(N - 1)] # Stores the answer ans = 0 # Stores absolute differences of # adjacent elements in new_Arr for i in range(N - 1): new_Arr[i] = abs(arr[i] - arr[i + 1]) # Stores the sum of all absolute # differences of adjacent elements ans += new_Arr[i] # Sorting the new_Arr # in decreasing order new_Arr = sorted(new_Arr)[::-1] for i in range(K - 1): # Removing K - 1 elements # with maximum sum ans -= new_Arr[i] # Prints the answer print (ans) # Driver code if __name__ == '__main__': # Given array arr[] arr = [ 1, 3, -2, 5, -1 ] # Given K K = 2 # Size of array N = len(arr) # Function Call absoluteDifference(arr, N, K) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
public static void reverse(int[] array)
{
// Length of the array
int n = array.Length;
// Swaping the first half elements with
// last half elements
for(int i = 0; i < n / 2; i++)
{
// Storing the first half elements
// temporarily
int temp = array[i];
// Assigning the first half to
// the last half
array[i] = array[n - i - 1];
// Assigning the last half to
// the first half
array[n - i - 1] = temp;
}
}
// Function to split an array into K subarrays
// with minimum sum of absolute difference
// of adjacent elements in each of K subarrays
public static void absoluteDifference(int[] arr,
int N, int K)
{
// Stores the absolute differences
// of adjacent elements
int[] new_Arr = new int[N - 1];
// Stores the answer
int ans = 0;
// Stores absolute differences of
// adjacent elements in new_Arr
for(int i = 0; i < N - 1; i++)
{
new_Arr[i] = Math.Abs(arr[i] -
arr[i + 1]);
// Stores the sum of all absolute
// differences of adjacent elements
ans += new_Arr[i];
}
// Sorting the new_Arr
// in decreasing order
Array.Sort(new_Arr);
reverse(new_Arr);
for(int i = 0; i < K - 1; i++)
{
// Removing K - 1 elements
// with maximum sum
ans -= new_Arr[i];
}
// Prints the answer
Console.WriteLine(ans);
}
// Driver Code
public static void Main ()
{
// Given array arr[]
int[] arr = { 1, 3, -2, 5, -1 };
// Given K
int K = 2;
// Size of array
int N = arr.Length;
// Function Call
absoluteDifference(arr, N, K);
}
}
// This code is contributed by susmitakundugoaldanga
Javascript
<script>
// Javascript program for the above approach
function reverse(array)
{
// Length of the array
let n = array.length;
// Swaping the first half elements
// with last half elements
for(let i = 0; i < n / 2; i++)
{
// Storing the first half
// elements temporarily
let temp = array[i];
// Assigning the first half
// to the last half
array[i] = array[n - i - 1];
// Assigning the last half
// to the first half
array[n - i - 1] = temp;
}
}
// Function to split an array into K subarrays
// with minimum sum of absolute difference
// of adjacent elements in each of K subarrays
function absoluteDifference(arr, N, K)
{
// Stores the absolute differences
// of adjacent elements
let new_Arr = new Array(N - 1).fill(0);
// Stores the answer
let ans = 0;
// Stores absolute differences of
// adjacent elements in new_Arr
for(let i = 0; i < N - 1; i++)
{
new_Arr[i] = Math.abs(arr[i] - arr[i + 1]);
// Stores the sum of all absolute
// differences of adjacent elements
ans += new_Arr[i];
}
// Sorting the new_Arr
// in decreasing order
new_Arr.sort();
reverse(new_Arr);
for(let i = 0; i < K - 1; i++)
{
// Removing K - 1 elements
// with maximum sum
ans -= new_Arr[i];
}
// Print the answer
document.write(ans);
}
// Driver Code
// Given array arr[]
let arr = [ 1, 3, -2, 5, -1 ];
// Given K
let K = 2;
// Size of array
let N = arr.length;
// Function Call
absoluteDifference(arr, N, K);
// This code is contributed by splevel62
</script>
Producción:
13
Complejidad de tiempo: O(N * Log(N))
Espacio auxiliar: O(N)