Maximice la suma de los elementos de la array eliminados realizando las operaciones dadas

Dadas dos arrays arr[] y min[] que consisten en N enteros y un entero K . Para cada índice i , arr[i] puede reducirse como máximo a min[i] . Considere una variable, digamos S ( inicialmente 0 ). La tarea es encontrar el valor máximo de S que se puede obtener realizando las siguientes operaciones:

• Elija un índice i y agregue max(arr[i], min[i]) a S .
• Elimina el elemento elegido de arr[] y su valor mínimo correspondiente.
• Disminuya cada valor restante en K si es mayor que su valor mínimo correspondiente en min[] .

Ejemplos:

Entrada: arr[] = {2, 4, 5, 8}, min[] = {1, 4, 5, 5}, K = 3
Salida: 18
Explicación:
Elija los elementos en el siguiente orden:
Paso 1: Elija elemento 8. Ahora, S = 8 y arr[] = {-1, 4, 5} y min[] = {1, 4, 5}
Paso 2: elige el elemento 5. Ahora, S = 8 + 5 = 13 y arr[] = {-1, 4} y min[] = {1, 4}
Paso 3: elige el elemento 5. Ahora, S = 8 + 5 + 4 = 17 y arr[] = {-1} y min[ ] = {1}
Paso 4: Elija el elemento -1, pero -1 < min[0]. Por lo tanto, elige 1.
Por lo tanto, S = 8 + 5 + 4 + 1 = 18.

Entrada: arr[] = {3, 5, 2, 1}, min[] = {3, 2, 1, 3}, K = 2
Salida:  12
Explicación:
Elija los elementos en el siguiente orden:
Paso 1: Elija elemento 5. Ahora, S = 5 y arr[] = {3, 0, 1} y min[] = {3, 1, 3}
Paso 2: Elija el elemento 3. Ahora, S = 5 + 3 = 8 y arr [] = {0, 1} y min[] = {1, 3} Paso 3: Elija el elemento 3 de min[]. Ahora, S = 5 + 3 + 3 = 11 y arr[] = {0} y min[] = {1} Paso 4: elige el elemento 1 de min[]. Por lo tanto, S = 5 + 3 + 3 + 1 = 12. 

Enfoque ingenuo: el enfoque más simple es atravesar la array dada y realizar las operaciones dadas en la array misma. Siga los pasos a continuación para resolver el problema:

1. Atraviese la array y encuentre el elemento máximo de la array .
2. Agregue el valor máximo en S y elimine el máximo.
3. Disminuya el elemento restante en K si cumplen las condiciones anteriores.
4. Repita los pasos anteriores hasta que la array dada quede vacía.
5. Después de atravesar, imprima S .

Complejidad de tiempo: O(N ² ), donde N es la longitud de la array dada.
Espacio Auxiliar: O(N)

Enfoque eficiente: la idea es ordenar la array dada en orden decreciente . Luego, imprima el valor máximo de S eligiendo los elementos con avidez. Siga los pasos a continuación para resolver el problema:

1. Empareje los elementos de la array arr[] con sus valores correspondientes en min[] .
2. Ordene la array de pares en orden decreciente de acuerdo con la array arr[] .
3. Inicialmente, elija el elemento máximo y aumente K por su valor inicial.
4. Ahora, elija el siguiente elemento máximo disminuyendo su valor por el K actual .
5. Repita los pasos anteriores, hasta que se atraviesen todos los elementos de la array e imprima el valor de S .

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 maximum sum of
// the array arr[] where each element
// can be reduced to at most min[i]
void findMaxSum(vector<int> arr, int n,
                vector<int> min, int k,
                int& S)
{
    // Stores the pair of arr[i] & min[i]
    vector<pair<int, int> > A;
 
    for (int i = 0; i < n; i++) {
        A.push_back({ arr[i], min[i] });
    }
 
    // Sorting vector of pairs
    sort(A.begin(), A.end(),
        greater<pair<int, int> >());
 
    int K = 0;
 
    // Traverse the vector of pairs
    for (int i = 0; i < n; i++) {
 
        // Add to the value of S
        S += max(A[i].first - K,
                A[i].second);
 
        // Update K
        K += k;
    }
}
 
// Driver Code
int main()
{
    vector<int> arr, min;
 
    // Given array arr[], min[]
    arr = { 3, 5, 2, 1 };
    min = { 3, 2, 1, 3 };
 
    int N = arr.size();
 
    // Given K
    int K = 3;
 
    int S = 0;
 
    // Function Call
    findMaxSum(arr, N, min, K, S);
 
    // Print the value of S
    cout << S;
 
    return 0;
}

// Java program for the
// above approach
import java.util.*;
  
class GFG{
     
static int S;
 
// Function to find the maximum sum of
// the array arr[] where each element
// can be reduced to at most min[i]
static void findMaxSum(int[] arr, int n,
                       int[] min, int k)
{
     
    // Stores the pair of arr[i] & min[i]
    ArrayList<int[]> A = new ArrayList<>();
  
    for(int i = 0; i < n; i++)
    {
        A.add(new int[]{arr[i], min[i]});
    }
  
    // Sorting vector of pairs
    Collections.sort(A, (a, b) -> b[0] - a[0]);
  
    int K = 0;
  
    // Traverse the vector of pairs
    for(int i = 0; i < n; i++)
    {
         
        // Add to the value of S
        S += Math.max(A.get(i)[0] - K,
                      A.get(i)[1]);
  
        // Update K
        K += k;
    }
}
 
// Driver code
public static void main (String[] args)
{
     
    // Given array arr[], min[]
    int[] arr = { 3, 5, 2, 1 };
    int[] min = { 3, 2, 1, 3 };
     
    int N = arr.length;
     
    // Given K
    int K = 3;
     
     S = 0;
     
    // Function Call
    findMaxSum(arr, N, min, K);
     
    // Print the value of S
    System.out.println(S);
}
}
 
// This code is contributed by offbeat

# Python3 program for the above approach
 
# Function to find the maximum sum of
# the array arr[] where each element
# can be reduced to at most min[i]
def findMaxSum(arr, n, min, k, S):
     
    # Stores the pair of arr[i] & min[i]
    A = []
 
    for i in range(n):
        A.append((arr[i], min[i]))
 
    # Sorting vector of pairs
    A = sorted(A)
    A = A[::-1]
     
    K = 0
 
    # Traverse the vector of pairs
    for i in range(n):
 
        # Add to the value of S
        S += max(A[i][0] - K, A[i][1])
 
        # Update K
        K += k
 
    return S
     
# Driver Code
if __name__ == '__main__':
     
    arr, min = [], []
 
    # Given array arr[], min[]
    arr = [ 3, 5, 2, 1 ]
    min = [ 3, 2, 1, 3 ]
 
    N = len(arr)
 
    # Given K
    K = 3
     
    S = 0
 
    # Function Call
    S = findMaxSum(arr, N, min, K, S)
 
    # Print the value of S
    print(S)
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
 
class GFG{
 
static int S;
 
// Function to find the maximum sum of
// the array arr[] where each element
// can be reduced to at most min[i]
static void findMaxSum(int[] arr, int n,
                       int[] min, int k)
{
     
    // Stores the pair of arr[i] & min[i]
    List<List<int>> A = new List<List<int>>();
    for(int i = 0; i < n; i++)
    {
        A.Add(new List<int>());
        A[i].Add(arr[i]);
        A[i].Add(min[i]);
    }
     
    // Sorting vector of pairs
    A = A.OrderBy(lst => lst[0]).ToList();
    A.Reverse();
     
    int K = 0;
     
    // Traverse the vector of pairs
    for(int i = 0; i < n; i++)
    {
         
        // Add to the value of S
        S += Math.Max(A[i][0] - K, A[i][1]);
         
        // Update K
        K += k;
    }
}
 
// Driver code
static public void Main()
{
     
    // Given array arr[], min[]
    int[] arr = { 3, 5, 2, 1 };
    int[] min = { 3, 2, 1, 3 };
  
    int N = arr.Length;
  
    // Given K
    int K = 3;
  
    S = 0;
  
    // Function Call
    findMaxSum(arr, N, min, K);
  
    // Print the value of S
    Console.WriteLine(S);
}
}
 
// This code is contributed by avanitrachhadiya2155

<script>
 
// Javascript program for the above approach
 
var S =0;
 
// Function to find the maximum sum of
// the array arr[] where each element
// can be reduced to at most min[i]
function findMaxSum(arr, n, min, k)
{
    // Stores the pair of arr[i] & min[i]
    var A = [];
 
    for (var i = 0; i < n; i++) {
        A.push([arr[i], min[i] ]);
    }
 
    // Sorting vector of pairs
    A.sort((a,b)=> b[0]-a[0]);
 
    var K = 0;
 
    // Traverse the vector of pairs
    for (var i = 0; i < n; i++) {
 
        // Add to the value of S
        S += Math.max(A[i][0] - K,
                A[i][1]);
 
        // Update K
        K += k;
    }
}
 
// Driver Code
var arr = [], min = [];
// Given array arr[], min[]
arr = [3, 5, 2, 1];
min = [3, 2, 1, 3];
var N = arr.length;
// Given K
var K = 3;
// Function Call
findMaxSum(arr, N, min, K, S);
// Print the value of S
document.write( S);
 
</script>

12

Complejidad de tiempo: O(N*log N), donde N es la longitud de la array dada.
Espacio Auxiliar: O(N)