Minimizar la suma de los valores absolutos de A[i] – (B + i) para una array dada

Dada una array arr[ ] de tamaño N, la tarea es encontrar el valor mínimo posible de la expresión abs(arr[1] – (b + 1)) + abs(arr[2] – (b + 2)) . . . abs(arr[N] – (b + N)) , donde b es un número entero independiente.

Entrada: arr[ ] = { 2, 2, 3, 5, 5 }
Salida: 2
Explicación:  Considerando b = 0: El valor de la expresión es abs(2 – (0 + 1)) + abs(2 – (0) + 2)) + abs(3 – (0 + 3)) + abs(5 – (0 + 4)) + abs(5 – (0 + 5)) = 1 + 0 + 0 + 1 + 0 = 2
Por lo tanto , el valor mínimo posible para la expresión es 2.

Entrada: arr[ ] = { 6, 5, 4, 3, 2, 1 }
Salida: 18

Enfoque: Considerando B[i] = A[i] − i, el problema es reducir al mínimo la suma de abs (B[i] − b). Se puede observar que es mejor tener b como la mediana del arreglo modificado B[]. Entonces, después de ordenar la array B[], el problema se puede resolver siguiendo los pasos que se detallan a continuación .

• Recorre la array arr[ ] y disminuye cada elemento por su índice (i + 1) .
• Ordene la array en orden ascendente .
• Ahora, elija b como la mediana de arr[ ] , digamos b = arr[N/2] .
• Inicialice una variable, digamos ans como 0, para almacenar el valor mínimo posible de la expresión.
• Atraviese la array de nuevo y actualice ans como abs(arr[i] – b).
• Devuelve el valor de ans .

A continuación se muestra la implementación del enfoque anterior.

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate minimum
// possible sum of all (arr[i] - b + i)
int MinSum(int arr[], int N)
{
 
    // Modify the array
    for (int i = 0; i < N; i++) {
        arr[i] = arr[i] - (i + 1);
    }
 
    // Sort the array
    sort(arr, arr + N);
 
    // Calculate median
    int b = arr[N / 2];
 
    // Stores the required answer
    int ans = 0;
    for (int i = 0; i < N; i++) {
 
        // Update answer
        ans += abs(arr[i] - b);
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
int main()
{
 
    // Given Input
    int arr[] = { 2, 2, 3, 5, 5 };
    int N = sizeof(arr) / sizeof(int);
 
    // Function Call
    int ans = MinSum(arr, N);
 
    cout << ans << "\n";
 
    return 0;
}

// Java program for above approach
// Function to calculate minimum
// possible sum of all (arr[i] - b + i)
import java.util.*;
class GFG{
     
static int MinSum(int arr[], int N)
{
 
    // Modify the array
    for (int i = 0; i < N; i++) {
        arr[i] = arr[i] - (i + 1);
    }
 
    // Sort the array
    Arrays.sort(arr);
 
    // Calculate median
    int b = arr[N / 2];
 
    // Stores the required answer
    int ans = 0;
    for (int i = 0; i < N; i++) {
 
        // Update answer
        ans += Math.abs(arr[i] - b);
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    // Given Input
    int arr[] = { 2, 2, 3, 5, 5 };
    int N = arr.length;
 
    // Function Call
    int ans = MinSum(arr, N);
 
    System.out.print(ans);
 
}
}
 
// This code is contributed by shivanisinghss2110

# Java program for above approach
# Function to calculate minimum
# possible sum of all (arr[i] - b + i)
def MinSum(arr, N):
   
  # Modify the array
    for i in range(N):
        arr[i] -= (i+1)
         
    # sort the array   
    arr.sort()
     
    # calculate median
    b = arr[N//2]
     
     # Stores the required answer
    ans = 0
    for i in range(N):
       
      # Update answer
        ans += abs(arr[i]-b)
         
        # Return the answer
    return ans
 
# Driver code
arr = [2, 2, 3, 5, 5]
N = len(arr)
print(MinSum(arr, N))
 
# This code is contributed by Parth Manchanda

// C# program for above approach
using System;
 
class GFG{
 
// Function to calculate minimum
// possible sum of all (arr[i] - b + i)
static int MinSum(int []arr, int N)
{
     
    // Modify the array
    for(int i = 0; i < N; i++)
    {
        arr[i] = arr[i] - (i + 1);
    }
 
    // Sort the array
    Array.Sort(arr);
 
    // Calculate median
    int b = arr[N / 2];
 
    // Stores the required answer
    int ans = 0;
    for(int i = 0; i < N; i++)
    {
         
        // Update answer
        ans += Math.Abs(arr[i] - b);
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
static void Main()
{
     
    // Given Input
    int []arr = { 2, 2, 3, 5, 5 };
    int N = arr.Length;
 
    // Function Call
    int ans = MinSum(arr, N);
 
    Console.Write(ans);
}
}
 
// This code is contributed by SoumikMondal

<script>
        // JavaScript Program for the above approach
 
        // Function to calculate minimum
        // possible sum of all (arr[i] - b + i)
        function MinSum(arr, N) {
 
            // Modify the array
            for (let i = 0; i < N; i++) {
                arr[i] = arr[i] - (i + 1);
            }
 
            // Sort the array
            arr.sort(function (a, b) { return a - b });
 
            // Calculate median
            let b = arr[Math.floor(N / 2)];
 
            // Stores the required answer
            let ans = 0;
            for (let i = 0; i < N; i++) {
 
                // Update answer
                ans += Math.abs(arr[i] - b);
            }
 
            // Return the answer
            return ans;
        }
 
        // Driver Code
 
        // Given Input
        let arr = [2, 2, 3, 5, 5];
        let N = arr.length;
 
        // Function Call
        let ans = MinSum(arr, N);
 
        document.write(ans + "<br>");
 
    // This code is contributed by Potta Lokesh
    </script>

2

Complejidad de tiempo: O(N*logN)
Espacio auxiliar: O(1)