Maximiser la somme des éléments du tableau supprimés en effectuant les opérations données

Étant donné deux tableaux arr[] et min[] composé de N entiers et un entier K. Pour chaque indice jearr[i] peut être réduit à tout au plus min[i]. Prenons une variable, disons S(initialement 0). La tâche consiste à trouver la valeur maximale de S que l’on peut obtenir en effectuant les opérations suivantes :

  • Choisissez un indice je et ajouter max(arr[i]min[i]) à S.
  • Supprimer l’élément choisi de arr[] et sa valeur minimale correspondante.
  • Diminuer chaque valeur restante de K s’il est supérieur à sa valeur minimale correspondante dans min[].

Exemples:

Saisir: arr[] = {2, 4, 5, 8}, min[] = {1, 4, 5, 5}, K = 3
Production: 18
Explication:
Choisissez les éléments dans l’ordre suivant :
Étape 1 : Choisissez l’élément 8. Maintenant, S = 8 et arr[] = {-1, 4, 5} et min[] = {1, 4, 5}
Étape 2 : Choisissez l’élément 5. Maintenant, S = 8 + 5 = 13 et arr[] = {-1, 4} et min[] = {1, 4}
Étape 3 : Choisissez l’élément 5. Maintenant, S = 8 + 5 + 4 = 17 et arr[] = {-1} et min[] = {1}
Étape 4 : Choisissez l’élément -1, mais -1 < min[0]. Par conséquent, choisissez 1.
Par conséquent, S = 8 + 5 + 4 + 1 = 18.

Saisir: arr[] = {3, 5, 2, 1}, min[] = {3, 2, 1, 3}, K = 2
Production: 12
Explication:
Choisissez les éléments dans l’ordre suivant :
Étape 1 : Choisissez l’élément 5. Maintenant, S = 5 et arr[] = {3, 0, 1} et min[] = {3, 1, 3}
Étape 2 : Choisissez l’élément 3. Maintenant, S = 5 + 3 = 8 et arr[] = {0, 1} et min[] = {1, 3}
Étape 3 : Choisissez l’élément 3 de min[]. Maintenant, S = 5 + 3 + 3 = 11 et arr[] = {0} et min[] = {1}
Étape 4 : Choisissez l’élément 1 de min[].
Par conséquent, S = 5 + 3 + 3 + 1 = 12.

Approche naïve : L’approche la plus simple consiste à parcourir le tableau donné et effectuer les opérations données dans le tableau lui-même. Suivez les étapes ci-dessous pour résoudre le problème :

  1. Traverser le tableau et trouver l’élément de tableau maximum.
  2. Ajouter la valeur maximale dans S et supprimer le maximum.
  3. Diminuer l’élément restant de K s’ils remplissent les conditions ci-dessus.
  4. Répétez les étapes ci-dessus jusqu’à ce que le tableau donné devienne vide.
  5. Après avoir traversé, imprimez S.

Complexité temporelle : SUR2), où N est la longueur du tableau donné.
Espace Auxiliaire : SUR)

Approche efficace : L’idée est de trier le tableau donné dans l’ordre décroissant. Ensuite, imprimez la valeur maximale de S en choisissant les éléments avec avidité. Suivez les étapes ci-dessous pour résoudre le problème :

  1. Associez les éléments du tableau arr[] avec leurs valeurs correspondantes dans min[].
  2. Trier le tableau de paires dans l’ordre décroissant selon le tableau arr[].
  3. Dans un premier temps, choisissez l’élément maximum et augmentez K par sa valeur initiale.
  4. Maintenant, choisissez le prochain élément maximum en diminuant sa valeur par le courant K.
  5. Répétez les étapes ci-dessus, jusqu’à ce que tous les éléments du tableau soient parcourus et imprimez la valeur de S.

Voici la mise en œuvre de l’approche ci-dessus :

C++

#include <bits/stdc++.h>

using namespace std;

void findMaxSum(vector<int> arr, int n,

                vector<int> min, int k,

                int& S)

{

    

    vector<pair<int, int> > A;

    for (int i = 0; i < n; i++) {

        A.push_back({ arr[i], min[i] });

    }

    

    sort(A.begin(), A.end(),

        greater<pair<int, int> >());

    int K = 0;

    

    for (int i = 0; i < n; i++) {

        

        S += max(A[i].first - K,

                A[i].second);

        

        K += k;

    }

}

int main()

{

    vector<int> arr, min;

    

    arr = { 3, 5, 2, 1 };

    min = { 3, 2, 1, 3 };

    int N = arr.size();

    

    int K = 3;

    int S = 0;

    

    findMaxSum(arr, N, min, K, S);

    

    cout << S;

    return 0;

}

Java

import java.util.*;

 

class GFG{

    

static int S;

static void findMaxSum(int[] arr, int n,

                       int[] min, int k)

{

    

    

    ArrayList<int[]> A = new ArrayList<>();

 

    for(int i = 0; i < n; i++)

    {

        A.add(new int[]{arr[i], min[i]});

    }

 

    

    Collections.sort(A, (a, b) -> b[0]- un[0]);

 

    int K = 0;

 

    

    for(int i = 0; i < n; i++)

    {

        

        

        S += Math.max(A.get(i)[0] -K,

                      A.get(i)[1]);

 

        

        K += k;

    }

}

public static void main (String[] args)

{

    

    

    int[] arr = { 3, 5, 2, 1 };

    int[] min = { 3, 2, 1, 3 };

    

    int N = arr.length;

    

    

    int K = 3;

    

     S = 0;

    

    

    findMaxSum(arr, N, min, K);

    

    

    System.out.println(S);

}

}

Python3

def findMaxSum(arr, n, min, k, S):

    

    

    A = []

    for i in range(n):

        A.append((arr[i], min[i]))

    

    A = sorted(A)

    A = UN[::-1]

    

    K = 0

    

    for i in range(n):

        

        S += max(UN[i][0] - K, A[i][1])

        

        K += k

    return S

    

if __name__ == '__main__':

    

    arr, min = [], []

    

    arr = [ 3, 5, 2, 1 ]

    min = [ 3, 2, 1, 3 ]

    N = len(arr)

    

    K = 3

    

    S = 0

    

    S = findMaxSum(arr, N, min, K, S)

    

    print(S)

C#

using System;

using System.Collections.Generic;

using System.Linq;

class GFG{

static int S;

static void findMaxSum(int[] arr, int n,

                       int[] min, int k)

{

    

    

    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]);

    }

    

    

    A = A.OrderBy(lst => lst[0]).ToList();

    A.Reverse();

    

    int K = 0;

    

    

    for(int i = 0; i < n; i++)

    {

        

        

        S += Math.Max(A[i][0] - K, A[i][1]);

        

        

        K += k;

    }

}

static public void Main()

{

    

    

    int[] arr = { 3, 5, 2, 1 };

    int[] min = { 3, 2, 1, 3 };

 

    int N = arr.Length;

 

    

    int K = 3;

 

    S = 0;

 

    

    findMaxSum(arr, N, min, K);

 

    

    Console.WriteLine(S);

}

}

Javascript

<script>

var S =0;

function findMaxSum(arr, n, min, k)

{

    

    var A = [];

    for (var i = 0; i < n; i++) {

        A.push([arr[i], min[i] ]);

    }

    

    A.sort((a,b)=> b[0]-a[0]);

    var K = 0;

    

    for (var i = 0; i < n; i++) {

        

        S += Math.max(A[i][0] - K,

                A[i][1]);

        

        K += k;

    }

}

var arr = [], min = [];

arr = [3, 5, 2, 1];

min = [3, 2, 1, 3];

var N = arr.length;

var K = 3;

findMaxSum(arr, N, min, K, S);

document.write( S);

</script>

Complexité temporelle : O(N*log N), où N est la longueur du tableau donné.
Espace Auxiliaire : SUR)

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Aller en haut