Somme maximale possible du tableau après avoir effectué l'opération donnée

Dans cette question, nous effectuerons l'opération donnée sur les éléments du tableau et trouverons la somme maximale finale.

Ici, dans chaque opération, nous pouvons sélectionner au plus X[p] éléments du tableau et les remplacer par des éléments Y[p] pour maximiser la somme.

Dans une méthode simple, nous trouverons les éléments du tableau X[p] qui sont plus petits que les éléments Y[p] et les remplacerons par Y[p].

Dans une approche efficace, nous utiliserons la file d'attente prioritaire pour obtenir la somme maximale.

Énoncé du problème− On nous donne un tableau nums[] contenant N nombres. En même temps, on nous donne des tableaux X[] et Y[] contenant M entiers. Nous devons effectuer les opérations suivantes sur le tableau nums[].

• Nous devons effectuer M opérations sur chacun des éléments X[] et Y[]. Dans chaque opération, nous devons sélectionner le plus grand élément X[p] du tableau nums[] et le remplacer par Y[p].

La tâche confiée est de trouver la somme maximale des éléments du tableau nums[] après avoir effectué M opérations.

Exemple Exemple

Entrez

nums[] = {10, 8, 7, 60, 20, 18, 30, 60}; m = 3; x[] = {1, 2, 5}; y[] = {500, 10, 2};

Sortie

708

Explication − Effectuons chaque opération une par une.

• Dans la première opération, nous remplacerons 7 éléments par 500. Ainsi, le tableau devient {10, 8, 500, 60, 20, 18, 30, 60}.

• Dans la deuxième opération, on peut remplacer jusqu'à 2 éléments par 10, mais on n'a qu'1 élément de moins que 10. Donc, on remplace 8 par 10 et le tableau devient {10, 10, 500, 60, 20, 18, 30, 60}.

• Dans la troisième opération, nous pouvons remplacer jusqu'à 5 éléments par 2, mais il n'y a pas d'éléments inférieurs à 2 dans le tableau. Nous ne remplacerons donc aucun élément.

Entrez

nums[] = {30, 40, 50, 50, 60}; m = 3; x[] = {2, 3, 6}; y[] = {10, 8, 21};

Sortie

230

Explication − Tous les éléments du tableau y[] sont plus petits que les éléments du tableau d'origine. Par conséquent, nous n’avons besoin de remplacer aucun élément du tableau donné pour obtenir la somme maximale.

Entrez

nums[] = {30, 40, 50, 50, 60}; m = 3; x[] = {2, 4, 5}; y[] = {50, 60, 100};

Sortie

500

Explication − Ici, nous pouvons remplacer jusqu'à x[p] éléments dans chaque opération. Lors de la dernière opération, nous pouvons remplacer chaque élément du tableau par 100, ce qui donne une somme maximale égale à 100.

Méthode 1

Dans cette méthode, nous allons parcourir les tableaux x[] et y[]. À chaque itération, nous trierons le tableau pour obtenir au plus x[p] éléments du tableau qui sont plus petits que les éléments y[p] et les remplacerons par y[p].

Algorithme

Étape 1 − Initialisez « maxSum » à 0, qui est utilisé pour stocker la somme maximale des éléments du tableau.

Étape 2 − Commencez à parcourir les éléments du tableau x[] et y[].

Étape 3 − Stockez la valeur de x[p] dans une variable temporaire et triez le tableau nums[].

Étape 4− Commencez à parcourir le tableau trié dans la boucle.

Étape 5 − Si la température est supérieure à 0 et que nums[q] est inférieur à y[p], mettez à jour nums[q] avec y[p] et décrémentez la valeur de température de 1.

Étape 6− En dehors de la boucle, commencez à parcourir le tableau mis à jour, retirez la somme de tous les éléments du tableau et stockez-la dans la variable maxSum.

Étape 7 − Renvoie maxSum à la fin de la fonction.

Exemple

#include <bits/stdc++.h>
using namespace std;

int getMaxSum(int nums[], int n, int q, int x[], int y[]) {
    int maxSum = 0;
    // Traverse X[] and Y[] array
    for (int p = 0; p < q; p++) {
        // Replacing x[p] number of elements of nums[] array with y[p] if they are lesser than y[p]
        int temp = x[p];
        sort(nums, nums + n);
        for (int q = 0; q < n; q++) {
            if (temp > 0 && nums[q] < y[p]) {
                nums[q] = y[p];
                temp--;
            }
        }
    }
    // Sum of the array
    for (int p = 0; p < n; p++) {
        maxSum += nums[p];
    }
    return maxSum;
}
int main() {
    int nums[] = {10, 8, 7, 60, 20, 18, 30, 60};
    int n = (sizeof nums) / (sizeof nums[0]);
    int m = 3;
    int x[] = {1, 2, 5};
    int y[] = {500, 10, 2};
    cout << "The maximum sum we can get by replacing the array values is " << getMaxSum(nums, n, m, x, y);
    return 0;
}

Sortie

The maximum sum we can get by replacing the array values is 708

Complexité temporelle− O(M*NlogN), où O(M) est utilisé pour parcourir toutes les requêtes et O(NlogN) est utilisé pour trier le tableau.

Complexité spatiale− Pour trier un tableau, la complexité spatiale est O(N).

Méthode 2

Dans cette méthode, nous utiliserons la file d'attente prioritaire pour stocker les paires d'éléments du tableau et leur nombre d'occurrences.

Par exemple, nous pousserons la paire {nums[p],1} dans la file d'attente prioritaire pour chaque élément du tableau. En même temps, nous poussons la paire {y[p], x[p]} dans la file d'attente prioritaire. Dans une file d'attente prioritaire, les paires seront triées en fonction du premier élément. Par conséquent, nous pouvons retirer les N premiers éléments de la file d’attente. Ici, pour la paire {y[p],x[p]}, nous pouvons retirer les éléments y[p] x[p] fois, et nous devons retirer un total de N éléments pour maximiser la somme.

Algorithme

Étape 1 − Initialisez le 'maxSum' avec 0 et la file d'attente prioritaire pour stocker la paire d'éléments et leur nombre d'occurrences.

Étape 2− Pour tous les éléments du tableau, insérez des paires {nums[p], 1} dans la file d'attente.

Étape 3 − Ensuite, insérez la paire {y[p], x[p]} dans la file d'attente prioritaire.

Étape 4− Répétez jusqu'à ce que n soit supérieur à 0.

Étape 4.1 − Supprimez le premier élément de la file d'attente prioritaire.

Étape 4.2 − Ajoutez first_ele * max(n, second_ele) à la somme. Ici, nous utilisons max(n, second_ele) pour gérer le dernier cas.

Étape 4.3 − Soustraire second_ele de n.

Étape 5− Renvoie maxSum.

Exemple

#include <bits/stdc++.h>
using namespace std;

int getMaxSum(int nums[], int n, int m, int x[], int y[]) {
    int maxSum = 0, p;
    // To get maximum sum
    priority_queue<pair<int, int>> p_que;
    // Insert nums[] array pairs into the queue
    for (p = 0; p < n; p++)
        p_que.push({nums[p], 1});
    // Push replacement pairs
    for (p = 0; p < m; p++)
        p_que.push({y[p], x[p]});
    // Add the first N elements of the priority queue in the sum
    while (n > 0) {
        // Get top element of priority queue
        auto temp = p_que.top();
        // Remove top element
        p_que.pop();
        // Add value to the sum
        maxSum += temp.first * min(n, temp.second);
        // Change N
        n -= temp.second;
    }
    return maxSum;
}
int main() {
    int nums[] = {10, 8, 7, 60, 20, 18, 30, 60};
    int n = (sizeof nums) / (sizeof nums[0]);
    int m = 3;
    int x[] = {1, 2, 5};
    int y[] = {500, 10, 2};
    cout << "The maximum sum we can get by replacing the array values is " << getMaxSum(nums, n, m, x, y);
    return 0;
}

Sortie

The maximum sum we can get by replacing the array values is 708

Complexité temporelle - O(N*logN + m*logm), où O(N) et O(m) sont utilisés pour parcourir le tableau donné et O(logN) sont utilisés pour insérer et supprimer des éléments dans la file d'attente.

Complexité spatiale - O(N+M) pour stocker les paires dans une file d'attente.

Dans la première méthode, nous devons trier le tableau à chaque itération pour trouver les plus petits éléments x[p]. Utilisez une file d'attente prioritaire pour trier automatiquement les éléments au fur et à mesure de leur insertion ou de leur suppression, car elle utilise la structure de données du tas. Par conséquent, cela améliore les performances de votre code.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!