Minimice el costo para llevar el elemento máximo a la posición K mediante el intercambio

Dados dos números enteros N y K y una array de N números enteros positivos (es decir, un ₀ , un ₁ , un ₂ …., un _n-1 ), la tarea es encontrar el costo mínimo para llevar el valor máximo a la K ^-ésima posición por intercambio (indexación basada en 1). El costo de intercambiar los elementos se define como la suma de los valores de los elementos de intercambio.

Ejemplo:

Entrada: N = 6, K= 4, arr[]= {3, 7, 8, 7, 4, 5}
Salida: 12
Explicación: Suma de arr[2] + arr[4]

Entrada: N= 8, K = 4, arr[]= {11, 31, 17, 18, 37, 14, 15, 11}
Salida: 0
Explicación: El máximo ya está en arr[4]

Enfoque:
La idea es encontrar la posición del elemento máximo si el elemento máximo no está en la K-ésima posición, luego intercambiarlo con el elemento que está en la K-ésima posición y la respuesta será el costo del elemento de intercambio, que es la suma de los valores de intercambio de elementos. si el elemento máximo está en la k-ésima posición, la respuesta será 0.

Siga los pasos a continuación para implementar la idea anterior:

• Encuentre la posición del elemento máximo.
• Compruebe si el elemento máximo está en la posición  Kth
  • Si es verdadero, devuelve 0 .
  • De lo contrario, intercambie el elemento máximo con el elemento en la posición Kth y devuelva la suma de los valores de los elementos de intercambio .

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

// C++ program to implement the idea:
#include <bits/stdc++.h>
using namespace std;
 
// Function to minimize cost to bring max at Kth
// position by swapping
int minimizeCost(int arr[], int N, int K)
{
 
    // Store maximum element in array
    int max_element = INT_MIN;
    int idx = -1;
 
    for (int i = 0; i < N; i++) {
        if (max_element < arr[i]) {
            max_element = arr[i];
            idx = i;
        }
    }
 
    if (idx == K)
        return 0;
 
    swap(arr[K], arr[idx]);
    return arr[K] + arr[idx];
}
 
// Driver Code
int main()
{
    int N = 6;
    int k = 4;
    int arr[N] = { 3, 7, 8, 7, 4, 5 };
 
    cout << minimizeCost(arr, N, k);
 
    return 0;
}

// Java program to implement the idea:
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to minimize cost to bring max at Kth
    // position by swapping
    public static int minimizeCost(int[] arr, int N, int K)
    {
 
        // Store maximum element in array
        int max_element = Integer.MIN_VALUE;
        int idx = -1;
 
        for (int i = 0; i < N; i++) {
            if (max_element < arr[i]) {
                max_element = arr[i];
                idx = i;
            }
        }
 
        if (idx == K)
            return 0;
 
        // swap
        int temp = arr[K];
        arr[K] = arr[idx];
        arr[idx] = temp;
 
        return arr[K] + arr[idx];
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 6;
        int k = 4;
        int[] arr = { 3, 7, 8, 7, 4, 5 };
 
        System.out.println(minimizeCost(arr, N, k));
    }
}
// This code is contributed by Ishan Khandelwal

# Python3 program to implement the idea:
 
# Function to minimize cost to bring max at Kth
# position by swapping
import sys
 
def minimizeCost(arr, N, K):
 
    # Store maximum element in array
    max_element = -sys.maxsize -1
    idx = -1
 
    for i in range(N):
        if (max_element < arr[i]):
            max_element = arr[i]
            idx = i
 
    if (idx == K):
        return 0
 
    arr[K], arr[idx] = arr[idx],arr[K]
    return arr[K] + arr[idx]
 
# Driver Code
N = 6
k = 4
arr = [ 3, 7, 8, 7, 4, 5 ]
 
print(minimizeCost(arr, N, k))
 
# This code is contributed by shinjanpatra

// C# program to implement the idea:
 
using System;
 
public class GFG {
 
  // Function to minimize cost to bring max at Kth
  // position by swapping
  public static int minimizeCost(int[] arr, int N, int K)
  {
 
    // Store maximum element in array
    int max_element = int.MinValue;
    int idx = -1;
 
    for (int i = 0; i < N; i++) {
      if (max_element < arr[i]) {
        max_element = arr[i];
        idx = i;
      }
    }
 
    if (idx == K)
      return 0;
 
    // swap
    int temp = arr[K];
    arr[K] = arr[idx];
    arr[idx] = temp;
 
    return arr[K] + arr[idx];
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    int N = 6;
    int k = 4;
    int[] arr = { 3, 7, 8, 7, 4, 5 };
 
    Console.WriteLine(minimizeCost(arr, N, k));
  }
}
// This code is contributed by AnkThon

<script>
        // JavaScript code for the above approach
 
        // Function to minimize cost to bring max at Kth
        // position by swapping
        function minimizeCost(arr, N, K) {
 
            // Store maximum element in array
            let max_element = Number.MIN_VALUE;
            let idx = -1;
 
            for (let i = 0; i < N; i++) {
                if (max_element < arr[i]) {
                    max_element = arr[i];
                    idx = i;
                }
            }
 
            if (idx == K)
                return 0;
 
            let temp = arr[k];
            arr[k] = arr[idx];
            arr[idx] = temp;
 
            return arr[K] + arr[idx];
        }
 
        // Driver Code
 
        let N = 6;
        let k = 4;
        let arr = [3, 7, 8, 7, 4, 5];
 
        document.write(minimizeCost(arr, N, k));
 
    // This code is contributed by Potta Lokesh
    </script>

12

Complejidad de tiempo:- O(N)
Espacio auxiliar:- O(1)