Incremento/decremento mínimo para hacer que la array no sea creciente

Dada una array a, su tarea es convertirla en una forma no creciente de modo que podamos incrementar o disminuir el valor de la array en 1 en los cambios mínimos posibles.

Ejemplos: 

Entrada: a[] = {3, 1, 2, 1}
Salida: 1
Explicación: podemos convertir la array en 3 1 1 1 cambiando el tercer elemento de la array, es decir, 2 en su entero anterior 1 en un paso, por lo tanto, solo un paso es requerido.

Entrada: a[] = {3, 1, 5, 1}
Salida: 4
Explicación: Necesitamos disminuir 5 a 1 para hacer que la array se ordene en orden no creciente.

Entrada: a[] = {1, 5, 5, 5}
Salida: 4
Explicación: Necesitamos aumentar 1 a 5.

Enfoque de fuerza bruta: consideramos ambas posibilidades para cada elemento y encontramos un mínimo de dos posibilidades. 

Método de enfoque eficiente 1 (usando Min-Heap):
Calcule la suma de las diferencias absolutas entre los elementos de la array final y los elementos de la array actual. Así, la respuesta será la suma de la diferencia entre el elemento i-ésimo y el elemento más pequeño que haya ocurrido hasta entonces. Para esto, podemos mantener un montón mínimo para encontrar el elemento más pequeño encontrado hasta ese momento. En la cola de prioridad mínima, pondremos los elementos, y los nuevos elementos se comparan con el mínimo anterior. Si se encuentra el nuevo mínimo, lo actualizaremos, esto se hace porque cada uno de los siguientes elementos que vienen deben ser más pequeños que el elemento mínimo actual encontrado hasta ahora. Aquí, calculamos la diferencia para que podamos obtener cuánto tenemos que cambiar el número actual para que sea igual o menor que los números anteriores encontrados. Por último,

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

// CPP code to count the change required to
// convert the array into non-increasing array
#include <bits/stdc++.h>
using namespace std;
 
int DecreasingArray(int a[], int n)
{
    int sum = 0, dif = 0;
 
    // min heap
    priority_queue<int, vector<int>, greater<int> > pq;
 
    // Here in the loop we will check that whether
    // the top of priority queue is less than
    // the upcoming array element. If yes then
    // we calculate the difference. After that
    // we will remove that element and push the
    // current element in queue. And the sum
    // is incremented by the value of difference
    for (int i = 0; i < n; i++) {
        if (!pq.empty() && pq.top() < a[i]) {
            dif = a[i] - pq.top();
            sum += dif;
 
            // Removing that minimum element
            // which does follow the decreasing
            // property and replacing it with a[i]
            // to maintain the condition
            pq.pop();
            pq.push(a[i]);
        }
 
        // Push the current element as well
        pq.push(a[i]);
    }
 
    return sum;
}
 
// Driver Code
int main()
{
    int a[] = { 3, 1, 2, 1 };
    int n = sizeof(a) / sizeof(a[0]);
 
    cout << DecreasingArray(a, n);
 
    return 0;
}

// Java code to count the change required to
// convert the array into non-increasing array
import java.util.PriorityQueue;
 
class GFG
{
    public static int DecreasingArray(int a[], int n)
    {
        int sum = 0, dif = 0;
 
        PriorityQueue<Integer> pq = new PriorityQueue<>();
 
        // Here in the loop we will
        // check that whether the upcoming
        // element of array is less than top
        // of priority queue. If yes then we
        // calculate the difference. After
        // that we will remove that element
        // and push the current element in
        // queue. And the sum is incremented
        // by the value of difference
        for (int i = 0; i < n; i++)
        {
            if (!pq.isEmpty() && pq.element() < a[i])
            {
                dif = a[i] - pq.element();
                sum += dif;
                pq.remove();
                  pq.add(a[i]);
            }
            pq.add(a[i]);
        }
     
    return sum;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
         
        int[] a = {3, 1, 2, 1};
         
        int n = a.length;
 
        System.out.println(DecreasingArray(a, n));
    }
}
 
// This Code is contributed by sanjeev2552

# Python3 code to count the change required to
# convert the array into non-increasing array
from queue import PriorityQueue
 
def DecreasingArray(a, n):
     
    ss, dif = (0,0)
     
    # min heap
    pq = PriorityQueue()
 
    # Here in the loop we will
    # check that whether the upcoming
    # element of array is less than top
    # of priority queue. If yes then we
    # calculate the difference. After
    # that we will remove that element
    # and push the current element in
    # queue. And the sum is incremented
    # by the value of difference
    for i in range(n):
        tmp = 0
         
        if not pq.empty():
            tmp = pq.get()
            pq.put(tmp)
         
        if not pq.empty() and tmp < a[i]:
            dif = a[i] - tmp
            ss += dif
            pq.get()
            pq.put(a[i])
         
        pq.put(a[i])
       
    return ss
     
# Driver code   
if __name__=="__main__":
     
    a = [ 3, 1, 2, 1 ]
    n = len(a)
  
    print(DecreasingArray(a, n))
     
# This code is contributed by rutvik_56

// C# code to count the change required to
// convert the array into non-increasing array
using System;
using System.Collections.Generic;
class GFG
{
    static int DecreasingArray(int[] a, int n)
    {
        int sum = 0, dif = 0;
      
        // min heap
        List<int> pq = new List<int>();
      
        // Here in the loop we will
        // check that whether the upcoming
        // element of array is less than top
        // of priority queue. If yes then we
        // calculate the difference. After
        // that we will remove that element
        // and push the current element in
        // queue. And the sum is incremented
        // by the value of difference
        for (int i = 0; i < n; i++)
        {
            if (pq.Count > 0 && pq[0] < a[i])
            {
                dif = a[i] - pq[0];
                sum += dif;
                pq.RemoveAt(0);
                  pq.Add(a[i]);
            }
            pq.Add(a[i]);
            pq.Sort();
        }
      
        return sum;
    }  
 
  // Driver code
  static void Main()
  {
    int[] a = { 3, 1, 2, 1 };
    int n = a.Length;
  
    Console.Write(DecreasingArray(a, n));
  }
}
 
// This code is contributed by divyeshrabadiya07.

<script>
 
// Javascript code to count the change required to
// convert the array into non-increasing array
function DecreasingArray(a, n)
{
    var sum = 0, dif = 0;
 
    // min heap
    var pq = [];
 
    // Here in the loop we will
    // check that whether the upcoming
    // element of array is less than top
    // of priority queue. If yes then we
    // calculate the difference. After
    // that we will remove that element
    // and push the current element in
    // queue. And the sum is incremented
    // by the value of difference
    for (var i = 0; i < n; i++)
    {
        if (pq.length != 0 && pq[pq.length - 1] < a[i]) {
            dif = a[i] - pq[pq.length - 1];
            sum += dif;
            pq.pop();
            pq.push(a[i]);
        }
        pq.push(a[i]);
        pq.sort((a, b)=>b - a);
    }
 
    return sum;
}
 
// Driver Code
var a = [3, 1, 2, 1];
var n = a.length;
document.write(DecreasingArray(a, n));
 
// This code is contributed by rrrtnx.
</script>

1

Complejidad de Tiempo: O(n log(n))  
Espacio Auxiliar: O(n)

Método 2: usar Max-Heap
Traverse en orden inverso en la array dada y mantener la propiedad creciente. Si algún elemento es más pequeño que el máximo de elementos existentes hasta ese índice, entonces, necesitamos hacer una operación de disminución en ese elemento máximo para que también siga la propiedad creciente del recorrido hacia atrás y agregue la operación requerida en la respuesta.

// CPP code to count the change required to
// convert the array into non-increasing array
#include <bits/stdc++.h>
using namespace std;
 
int DecreasingArray(int arr[], int n)
{
    int ans = 0;
 
    // max heap
    priority_queue<int> pq;
 
    // Here in the loop we will
    // check that whether the top
    // of priority queue is greater than the upcoming array
    // element. If yes then we calculate the difference.
    // After that we will remove that element and push the
    // current element in queue. And the sum is incremented
    // by the value of difference
 
    for (int i = n - 1; i >= 0; i--) {
        if (!pq.empty() and pq.top() > arr[i]) {
            ans += abs(arr[i] - pq.top());
            pq.pop();
            pq.push(arr[i]);
        }
        pq.push(arr[i]);
    }
    return ans;
}
 
// Driver Code
int main()
{
    int a[] = { 3, 1, 2, 1 };
    int n = sizeof(a) / sizeof(a[0]);
 
    cout << DecreasingArray(a, n);
 
    return 0;
}

// Java code to count the change required to
// convert the array into non-increasing array
import java.io.*;
import java.util.*;
 
class GFG {
    public static int DecreasingArray(int arr[], int n)
    {
        int ans = 0;
 
        // max heap
        PriorityQueue<Integer> pq = new PriorityQueue<>(
            Collections.reverseOrder());
 
        // Here in the loop we will
        // check that whether the top
        // of priority queue is greater than the upcoming
        // array element. If yes then we calculate the
        // difference. After that we will remove that
        // element and push the current element in queue.
        // And the sum is incremented by the value of
        // difference
 
        for (int i = n - 1; i >= 0; i--) {
            if (!pq.isEmpty() && pq.peek() > arr[i]) {
                ans += Math.abs(arr[i] - pq.peek());
                pq.poll();
                pq.add(arr[i]);
            }
            pq.add(arr[i]);
        }
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int a[] = { 3, 1, 2, 1 };
        int n = a.length;
 
        System.out.print(DecreasingArray(a, n));
    }
}
 
// This code is contributed by Rohit Pradhan

Producción:

1

Complejidad de Tiempo: O(n log(n)) 
Espacio Auxiliar: O(n)

Ver también: Convertir a una array estrictamente creciente con cambios mínimos.