Inversiones máximas en una secuencia de 1 a N después de realizar operaciones dadas como máximo K veces

Dados dos números enteros N y K , la tarea es encontrar el número máximo de inversión en una secuencia de primeros N números naturales después de realizar al máximo K operaciones. En cada operación, se pueden intercambiar dos elementos cualesquiera de la secuencia. Nota: los elementos de la secuencia están dispuestos en orden ascendente y no hay elementos repetidos en la secuencia.
Ejemplo: 
 

Entrada: N = 5, K = 3 
Salida: 10 
Explicación: 
Inicialmente tenemos la secuencia como {1, 2, 3, 4, 5}. 
En la primera operación, podemos intercambiar 1 y 5, por lo que la secuencia se convierte en {5, 2, 3, 4, 1}. 
En la segunda operación, podemos intercambiar 2 y 4, por lo que la secuencia se convierte en {5, 4, 3, 2, 1}. 
No requerimos más operaciones. Por lo tanto, el número de inversiones en la secuencia anterior es 10
Entrada: N = 4, K = 1 
Salida: 5 
Explicación: 
Inicialmente tenemos la secuencia como { 1, 2, 3, 4}. 
En la primera operación podemos intercambiar 1 y 4, por lo que la secuencia se convierte en {4, 2, 3, 1}. 
Dado que solo podemos realizar 1 operación, esta es nuestra secuencia final. Por lo tanto, el número de inversiones en la secuencia anterior es 5. 
 

Acercarse: 
 

1. Dado que los elementos dispuestos en orden ascendente son perfectos, es decir, tienen una inversión de 0 y los elementos dispuestos en orden descendente son menos perfectos, es decir, tienen una inversión máxima.
2. Entonces, la idea es hacer que la secuencia se acerque más al orden descendente con cada operación de intercambio para obtener inversiones máximas. Por lo tanto, en la primera operación, necesitamos intercambiar el elemento más grande y el más pequeño. De manera similar, en la i-ésima operación, necesitamos intercambiar el i-ésimo elemento más grande con el i-ésimo elemento más pequeño de la secuencia.
3. El número de intercambios necesarios para convertir la secuencia en orden ascendente en orden descendente es N/2 . Por lo tanto, el número de operaciones realizadas debe ser menor o igual a N/2 . 
   Entonces actualice K como:

 
 

K = min ( K, N / 2 )

 

1. Necesitamos mantener dos variables ‘izquierda’ y ‘derecha’ para representar el i-ésimo elemento mínimo y el i-ésimo máximo de la secuencia respectivamente.
2. Inicialice ‘left’ en 1 y ‘right’ en N .
3. Necesitamos realizar las siguientes operaciones hasta que K se convierta en 0: 
   • Activado, el intercambio de ‘izquierda’ y ‘derecha’ en el número de secuencia de inversión aumenta en 
      

 
 

2 * (izquierda – derecha) – 1 
 

 

• Entonces, agregue este valor a la respuesta. 
  • Esto se debe a que cuando intercambiamos ‘izquierda’ y ‘derecha’, todos los pares de la forma (derecha, i) contribuyen a las inversiones y también todos los pares de la forma (i, izquierda) contribuyen a las inversiones, donde izquierda < i < Correcto.
  • Número total de pares de la forma (derecha, i) => derecha – izquierda, donde izquierda <= i < derecha
  • Número total de pares de la forma (i, izquierda) => derecha – izquierda, donde izquierda< i <=derecha
  • El número total de tales pares es 2 * (derecha – izquierda)
  • Le restamos 1, porque el par (derecha, izquierda) se contó dos veces en el cálculo anterior.
• Disminuya el valor de K y ‘derecha’ en 1 y aumente ‘izquierda’ en 1.

1. Imprimir el valor de la respuesta

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 which computes the
// maximum number of inversions
int maximum_inversion(int n, int k)
{
    // 'answer' will store the required
    // number of inversions
    int answer = 0;
 
    // We do this because we will
    // never require more than
    // floor(n/2) operations
    k = min(k, n / 2);
 
    // left pointer in the array
    int left = 1;
    // right pointer in the array
    int right = n;
 
    // Doing k operations
    while (k--) {
        // Incrementing ans by number
        // of inversions increase due
        // to this swapping
        answer += 2 * (right - left) - 1;
        left++;
        right--;
    }
    cout << answer << endl;
}
 
// Driver code
int main()
{
    // Input 1
    int N = 5;
    int K = 3;
    maximum_inversion(N, K);
 
    // Input 2
    N = 4;
    K = 1;
    maximum_inversion(N, K);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// Function which computes the
// maximum number of inversions
static void maximum_inversion(int n, int k)
{
     
    // 'answer' will store the required
    // number of inversions
    int answer = 0;
 
    // We do this because we will
    // never require more than
    // floor(n/2) operations
    k = Math.min(k, n / 2);
 
    // left pointer in the array
    int left = 1;
     
    // right pointer in the array
    int right = n;
 
    // Doing k operations
    while (k != 0)
    {
        k--;
         
        // Incrementing ans by number
        // of inversions increase due
        // to this swapping
        answer += 2 * (right - left) - 1;
        left++;
        right--;
    }
    System.out.println(answer);
}
 
// Driver Code
public static void main(String s[])
{
     
    // Input 1
    int N = 5;
    int K = 3;
    maximum_inversion(N, K);
     
    // Input 2
    N = 4;
    K = 1;
    maximum_inversion(N, K);
}
}
 
// This code is contributed by rutvik_56

# Python3 program for the above approach
 
# Function which computes the
# maximum number of inversions
def maximum_inversion(n, k):
     
    # 'answer' will store the required
    # number of inversions
    answer = 0;
 
    # We do this because we will
    # never require more than
    # floor(n/2) operations
    k = min(k, n // 2);
 
    # left pointer in the array
    left = 1;
 
    # right pointer in the array
    right = n;
 
    # Doing k operations
    while (k > 0):
        k -= 1;
 
        # Incrementing ans by number
        # of inversions increase due
        # to this swapping
        answer += 2 * (right - left) - 1;
        left += 1;
        right -= 1;
 
    print(answer);
 
# Driver Code
if __name__ == '__main__':
     
    # Input 1
    N = 5;
    K = 3;
    maximum_inversion(N, K);
 
    # Input 2
    N = 4;
    K = 1;
    maximum_inversion(N, K);
 
# This code is contributed by amal kumar choubey

// C# program for the above approach
using System;
 
class GFG{
     
// Function which computes the
// maximum number of inversions
static void maximum_inversion(int n, int k)
{
     
    // 'answer' will store the required
    // number of inversions
    int answer = 0;
 
    // We do this because we will
    // never require more than
    // floor(n/2) operations
    k = Math.Min(k, n / 2);
 
    // left pointer in the array
    int left = 1;
     
    // right pointer in the array
    int right = n;
 
    // Doing k operations
    while (k != 0)
    {
        k--;
         
        // Incrementing ans by number
        // of inversions increase due
        // to this swapping
        answer += 2 * (right - left) - 1;
        left++;
        right--;
    }
    Console.WriteLine(answer);
}
 
// Driver Code
public static void Main(String []s)
{
     
    // Input 1
    int N = 5;
    int K = 3;
    maximum_inversion(N, K);
     
    // Input 2
    N = 4;
    K = 1;
    maximum_inversion(N, K);
}
}
 
// This code is contributed by Rohit_ranjan

<script>
// javascript program for the above approach
 
    // Function which computes the
    // maximum number of inversions
    function maximum_inversion(n, k) {
 
        // 'answer' will store the required
        // number of inversions
        var answer = 0;
 
        // We do this because we will
        // never require more than
        // floor(n/2) operations
        k = Math.min(k, parseInt(n / 2));
 
        // left pointer in the array
        var left = 1;
 
        // right pointer in the array
        var right = n;
 
        // Doing k operations
        while (k > 0)
        {
            k--;
 
            // Incrementing ans by number
            // of inversions increase due
            // to this swapping
            answer += 2 * (right - left) - 1;
            left++;
            right--;
        }
        document.write(answer + "<br/>");
    }
 
    // Driver Code
 
        // Input 1
        var N = 5;
        var K = 3;
        maximum_inversion(N, K);
 
        // Input 2
        N = 4;
        K = 1;
        maximum_inversion(N, K);
 
// This code is contributed by aashish1995
</script>

10
5

Complejidad temporal: O(K)  
Espacio auxiliar: O(1)