Minimice el costo de ordenar una array determinada ordenando subarreglos no ordenados

Dada una array arr[] de tamaño N , la tarea es minimizar el costo de ordenar la array clasificando cualquier subarreglo no ordenado donde el costo de la operación es la diferencia entre el elemento máximo y mínimo de ese subarreglo. Esta operación se puede realizar infinitas veces incluyendo 0.

Ejemplos:

Entrada: arr[] = {1, 7, 5, 2, 1, 8}
Salida: 6
Explicación: El subarreglo del índice [1,4] se puede elegir y ordenar con costo = 7 – 1 = 6

Entrada: arr[] = { 1, 4, 3, 5, 6 ,13, 10}
Salida: 4
Explicación:  El subarreglo del índice index [1,2] y [5,6] se puede ordenar con un costo de 4 – 3 y 13 – 10 = 1 + 3 = 4

Enfoque: Esto se puede resolver utilizando el enfoque codicioso , los elementos ya ordenados no requieren ningún costo, por lo que solo los subarreglos que tienen elementos no ordenados deben considerarse para ordenar. Multiset se puede usar para almacenar los elementos que no están ordenados y la diferencia entre el último y el primer elemento de multiset da el costo.

Siga estos pasos para resolver el problema anterior:

• Inicialice un vector v y copie el arr en él y asigne el tamaño del vector a la variable n.
• Ahora ordene el vector v .
• Inicialice 2 multisets m1 y m2 para almacenar el subarreglo ordenado y no ordenado respectivamente y cost = 0  para almacenar el resultado.
• Ahora itere a través del rango [0,N) y verifique
• Si v[i] no es igual a arr[i] 
• Inserte arr[i] en m1 y v[i] en m2
• Cuando ambos conjuntos múltiples son iguales, agregue la diferencia entre el último y el primer elemento del conjunto al costo .
• Borre ambos conjuntos múltiples para que los utilice el siguiente subarreglo no ordenado.
• Imprime el costo .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum cost
// to sort the array in ascending order
int minimum_cost(vector<int> arr)
{
    // Copy the arr into vector and sort it
    vector<int> sorted = arr;
    int n = arr.size();
    sort(sorted.begin(), sorted.end());
 
    // Initialize the two multisets to store
    // sorted and the unordered elements
    multiset<int> m1, m2;
 
    // Initialize cost to store final answer
    int cost = 0;
 
    for (int i = 0; i < n; i++) {
        if (sorted[i] != arr[i]) {
            m1.insert(arr[i]);
            m2.insert(sorted[i]);
 
            // If both the multisets are equal,
            // the unordered subarray is sorted
            if (m1 == m2) {
                // The cost is difference
                // between mini and max
                cost += (*m1.rbegin() -
                         *m2.begin());
 
                // Clear the multisets to make
                // use of it again
                m1.clear();
                m2.clear();
            }
        }
    }
    return cost;
}
 
// Driver code
int main()
{
    // Initialize the queries
    vector<int> arr = { 1, 7, 5, 2, 1, 8 };
    cout << minimum_cost(arr);
 
    return 0;
}

// Java code to implement the above approach
import java.util.*;
 
class GFG {
 
  // Function to find the minimum cost
  // to sort the array in ascending order
  public static int minimum_cost(int[] arr)
  {
 
    // Copy the arr into vector and sort it
    int n = arr.length;
    int[] sorted = new int[n];
    sorted = arr.clone();
    Arrays.sort(sorted);
 
    // Initialize the two multisets to store
    // sorted and the unordered elements
    SortedSet<Integer> m1 = new TreeSet<Integer>();
    SortedSet<Integer> m2 = new TreeSet<Integer>();
 
    // Initialize cost to store final answer
    int cost = 0;
 
    for (int i = 0; i < n; i++) {
      if (sorted[i] != arr[i]) {
        m1.add(arr[i]);
        m2.add(sorted[i]);
 
        // If both the multisets are equal,
        // the unordered subarray is sorted
        if (m1.equals(m2))
        {
 
          // The cost is difference
          // between mini and max
          cost += (Collections.max(m1) - Collections.min(m2));
 
          // Clear the multisets to make
          // use of it again
          m1.clear();
          m2.clear();
        }
      }
    }
    return cost;
  }
 
  // Driver code
  public static void main (String[] args)
  {
     
    // Initialize the queries
    int[] arr = { 1, 7, 5, 2, 1, 8 };
    System.out.println(minimum_cost(arr));
 
  }
}
 
// This code is contributed by Shubham Singh

# python3 program for the above approach
 
# Function to find the minimum cost
# to sort the array in ascending order
def minimum_cost(arr):
 
    # Copy the arr into vector and sort it
    sorted = arr.copy()
    n = len(arr)
    sorted.sort()
 
    # Initialize the two multisets to store
    # sorted and the unordered elements
    m1 = set()
    m2 = set()
 
    # Initialize cost to store final answer
    cost = 0
 
    for i in range(0, n):
        if (sorted[i] != arr[i]):
            m1.add(arr[i])
            m2.add(sorted[i])
 
            # If both the multisets are equal,
            # the unordered subarray is sorted
            if (m1 == m2):
                # The cost is difference
                # between mini and max
                cost += (list(m1)[len(list(m1)) - 1] -
                         list(m2)[0])
 
                # Clear the multisets to make
                # use of it again
                m1.clear()
                m2.clear()
 
    return cost
 
# Driver code
if __name__ == "__main__":
 
    # Initialize the queries
    arr = [1, 7, 5, 2, 1, 8]
    print(minimum_cost(arr))
 
    # This code is contributed by rakeshsahni

// C# code to implement the above approach
using System;
using System.Collections.Generic;
 
public class GFG{
 
  // Function to find the minimum cost
  // to sort the array in ascending order
  public static int minimum_cost(int[] arr)
  {
 
    // Copy the arr into vector and sort it
    int n = arr.Length;
    int[] sorted = new int[n];
    Array.Copy(arr, 0, sorted, 0, n);
    Array.Sort(sorted);
 
    // Initialize the two multisets to store
    // sorted and the unordered elements
    SortedSet<int> m1 = new SortedSet<int>();
    SortedSet<int> m2 = new SortedSet<int>();
 
    // Initialize cost to store final answer
    int cost = 0;
 
    for (int i = 0; i < n; i++) {
      if (sorted[i] != arr[i]) {
        m1.Add(arr[i]);
        m2.Add(sorted[i]);
 
        // If both the multisets are equal,
        // the unordered subarray is sorted
        if (m1.SetEquals(m2))
        {
 
          // The cost is difference
          // between mini and max
          cost += (m1.Max - m2.Min);
 
          // Clear the multisets to make
          // use of it again
          m1.Clear();
          m2.Clear();
        }
      }
    }
    return cost;
  }
 
  // Driver code
  public static void Main()
  {
    // Initialize the queries
    int[] arr = { 1, 7, 5, 2, 1, 8 };
    Console.Write(minimum_cost(arr));
 
  }
}
 
// This code is contributed by Shubham Singh

<script>
 
// Javascript program for the above approach
 
// Function to find the minimum cost
// to sort the array in ascending order
function minimum_cost(arr)
{
    // Copy the arr into vector and sort it
    var sorted = arr.slice();
    var n = arr.length;
    sorted.sort();
 
    // Initialize the two multisets to store
    // sorted and the unordered elements
    var m1 = new Set();
    var m2 = new Set();
 
    // Initialize cost to store final answer
    var cost = 0;
     
    let areSetsEqual = (a, b) => a.size === b.size && [...a].every(value => b.has(value));
     
    for (var i = 0; i < n; i++) {
        if (sorted[i] != arr[i]) {
            m1.add(arr[i]);
            m2.add(sorted[i]);
 
            // If both the multisets are equal,
            // the unordered subarray is sorted
            if (areSetsEqual(m1,m2)) {
                // The cost is difference
                // between mini and max
                cost += (Math.max(...Array.from(m1.values())) -
                         Math.min(...Array.from(m2.values())));
 
                // Clear the multisets to make
                // use of it again
                m1.clear();
                m2.clear();
            }
        }
    }
    return cost;
}
 
// Driver code
// Initialize the queries
var arr = [ 1, 7, 5, 2, 1, 8 ];
document.write(minimum_cost(arr));
 
// This code is contributed by Shubham Singh
</script>

6

Complejidad de Tiempo: O(N * logN ) 
Espacio Auxiliar: O(N)