Coût minimum pour vider un tableau où le coût de suppression d’un élément est de 2^(removed_count) * arr[i]

Afficher la discussion

Améliorer l’article

Enregistrer l’article

J’aime l’article

Afficher la discussion

Améliorer l’article

Enregistrer l’article

J’aime l’article

Étant donné un tableau arr[], la tâche consiste à trouver le coût minimum pour supprimer tous les éléments du tableau où le coût de suppression d’un élément est 2^j * arr[i]. Ici, j est le nombre d’éléments qui ont déjà été supprimés.

Exemples:

Saisir: arr[] = {3, 1, 3, 2}
Production: 25
Explication:
Supprimez d’abord 3. Coût = 2^(0)*3 = 3
Puis supprimez 3. Coût = 2^(1)*3 = 6
Puis supprimez 2. Coût = 2^(2)*2 = 8
Enfin, supprimez 1. Coût = 2^(3)*1 = 8
Coût total = 3 + 6 + 8 + 8 = 25

Saisir: arr[] = {1, 2}
Production: 4
Explication:
Supprimez d’abord 2. Coût = 2^(0)*2 = 2
Puis supprimez 1. Coût = 2^(1)*1 = 2
Coût total = 2 + 2 = 4

Approcher: L’idée est d’utiliser un paradigme de la programmation gourmande pour résoudre ce problème.
Il faut minimiser l’expression ( 2^j * arr[i] ). Cela peut être fait par :

  • Triez le tableau par ordre décroissant.
  • Multipliez pow(2, i) avec chaque élément i, en partant de 0 jusqu’à la taille du tableau.

Par conséquent, le coût total de la suppression d’éléments du tableau est donné par :

\text{Coût total = }arr[0]*2^{0} + arr[1] * 2^{1} + .... arr[n]*2^{n}

lorsque le tableau est en ordre décroissant.

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

C++

#include <bits/stdc++.h>

using namespace std;

#define ll long long int

int removeElements(ll arr[], int n)

{

    

    sort(arr, arr + n, greater<int>());

    ll ans = 0;

    

    

    

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

        ans += arr[i] * pow(2, i);

    }

    return ans;

}

int main()

{

    int n = 4;

    ll arr[n] = { 3, 1, 2, 3 };

    

    cout << removeElements(arr, n);

}

Java

import java.util.*;

class GFG{

static long[] reverse(long a[])

{

    int i, n = a.length;

    long t;

    

    for(i = 0; i < n / 2; i++)

    {

        t = a[i];

        un[i] = un[n - i - 1];

        un[n - i - 1] = t ;

    }

    return a;

}

static long removeElements(long arr[],

                           int n)

{

    

    

    Arrays.sort(arr);

    arr = reverse(arr);

    long ans = 0;

    

    

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

    {

        ans += arr[i] * Math.pow(2, i);

    }

    return ans;

}

public static void main(String[] args)

{

    int n = 4;

    long arr[] = { 3, 1, 2, 3 };

    

    System.out.print(removeElements(arr, n));

}

}

Python3

def removeElements(arr, n):

    

    arr.sort(reverse = True)

    ans = 0

    

    

    for i in range(n):

        ans += arr[i] * pow(2, i)

    return ans

if __name__ == "__main__":

    

    n = 4

    arr = [ 3, 1, 2, 3 ]

    

    print(removeElements(arr, n))

    

C#

using System;

class GFG{

static long[] reverse(long []a)

{

    int i, n = a.Length;

    long t;

    

    for(i = 0; i < n / 2; i++)

    {

        t = a[i];

        a[i] = a[n - i - 1];

        a[n - i - 1] = t;

    }

    return a;

}

static long removeElements(long []arr,

                           int n)

{

    

    

    Array.Sort(arr);

    arr = reverse(arr);

    long ans = 0;

    

    

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

    {

        ans += (long)(arr[i] * Math.Pow(2, i));

    }

    return ans;

}

public static void Main(String[] args)

{

    int n = 4;

    long []arr = { 3, 1, 2, 3 };

    

    Console.Write(removeElements(arr, n));

}

}

Javascript

<script>

      

      

      

      

      

      

      function removeElements(arr, n) {

        

        arr.sort((a, b) => b - a);

        var ans = 0;

        

        

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

          ans += arr[i] * Math.pow(2, i);

        }

        return ans;

      }

      

      var n = 4;

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

      

      document.write(removeElements(arr, n));

</script>

Complexité temporelle: O(N * log N)
Espace auxiliaire: O(1)

Laisser un commentaire

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