Maximal mögliche Array-Summe nach Ausführung der angegebenen Operation

In dieser Frage führen wir die angegebene Operation an den Array-Elementen durch und ermitteln die endgültige Maximalsumme.

Hier können wir in jeder Operation höchstens X[p] Elemente aus dem Array auswählen und sie durch Y[p] Elemente ersetzen, um die Summe zu maximieren.

Mit einer einfachen Methode finden wir X[p]-Array-Elemente, die kleiner als Y[p]-Elemente sind, und ersetzen sie durch Y[p].

Bei einem effizienten Ansatz verwenden wir die Prioritätswarteschlange, um die maximale Summe zu erhalten.

Problemstellung− Wir erhalten ein nums[]-Array mit N Zahlen. Gleichzeitig erhalten wir X[]- und Y[]-Arrays mit M ganzen Zahlen. Wir müssen die folgenden Operationen für das Array nums[] ausführen.

• Wir müssen M Operationen für jedes der X[]- und Y[]-Elemente ausführen. Bei jeder Operation müssen wir das größte X[p]-Element aus dem Array nums[] auswählen und es durch Y[p] ersetzen.

Die gegebene Aufgabe besteht darin, die maximale Summe der Elemente des Arrays nums[] nach der Durchführung von M-Operationen zu ermitteln.

Beispiel Beispiel

Eintreten

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

Ausgabe

708

Erklärung − Lassen Sie uns jeden Vorgang einzeln ausführen.

• Im ersten Arbeitsgang werden wir 7 Elemente durch 500 ersetzen. Das Array wird also zu {10, 8, 500, 60, 20, 18, 30, 60}.

• Im zweiten Vorgang können wir bis zu 2 Elemente durch 10 ersetzen, aber wir haben nur 1 Element weniger als 10. Wir ersetzen also 8 durch 10 und das Array wird zu {10, 10, 500, 60, 20, 18, 30, 60}.

• In der dritten Operation können wir bis zu 5 Elemente durch 2 ersetzen, aber es gibt keine Elemente mit weniger als 2 im Array. Daher werden wir keine Elemente ersetzen.

Eintreten

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

Ausgabe

230

Erklärung − Alle Elemente des y[]-Arrays sind kleiner als die Elemente des ursprünglichen Arrays. Daher müssen wir kein Element des angegebenen Arrays ersetzen, um die maximale Summe zu erhalten.

Eintreten

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

Ausgabe

500

Erklärung − Hier können wir in jeder Operation bis zu x[p] Elemente ersetzen. In der letzten Operation können wir jedes Element im Array durch 100 ersetzen, was zu einer maximalen Summe von 100 führt.

Methode 1

Bei dieser Methode iterieren wir über die Arrays x[] und y[]. In jeder Iteration sortieren wir das Array, um höchstens x[p] Array-Elemente zu erhalten, die kleiner als y[p]-Elemente sind, und ersetzen sie durch y[p].

Algorithmus

Schritt 1 − Initialisieren Sie „maxSum“ auf 0, was zum Speichern der maximalen Summe von Array-Elementen verwendet wird.

Schritt 2 − Beginnen Sie mit dem Durchlaufen der Array-Elemente x[] und y[].

Schritt 3 − Speichern Sie den Wert von x[p] in einer temporären Variablen und sortieren Sie das Array nums[].

Schritt 4− Beginnen Sie mit dem Durchlaufen des sortierten Arrays innerhalb der Schleife.

Schritt 5 − Wenn die Temperatur größer als 0 und nums[q] kleiner als y[p] ist, aktualisieren Sie nums[q] mit y[p] und verringern Sie den Temperaturwert um 1.

Schritt 6− Beginnen Sie außerhalb der Schleife mit dem Durchlaufen des aktualisierten Arrays, nehmen Sie die Summe aller Array-Elemente heraus und speichern Sie sie in der Variablen maxSum.

Schritt 7 − Geben Sie maxSum am Ende der Funktion zurück.

Beispiel

#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;
}

Ausgabe

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

Zeitkomplexität− O(M*NlogN), wobei O(M) zum Durchlaufen aller Abfragen und O(NlogN) zum Sortieren des Arrays verwendet wird.

Raumkomplexität− Für das Sortieren eines Arrays ist die Raumkomplexität O(N).

Methode 2

Bei dieser Methode verwenden wir die Prioritätswarteschlange, um die Paare von Array-Elementen und deren Vorkommensanzahl zu speichern.

Zum Beispiel werden wir das Paar {nums[p],1} für jedes Array-Element in die Prioritätswarteschlange verschieben. Gleichzeitig schieben wir das Paar {y[p], x[p]} in die Prioritätswarteschlange. In einer Prioritätswarteschlange werden Paare nach dem ersten Element sortiert. Daher können wir die obersten N Elemente aus der Warteschlange nehmen. Hier können wir für das Paar {y[p],x[p]} die y[p]-Elemente x[p]-mal herausnehmen und müssen insgesamt N Elemente herausnehmen, um die Summe zu maximieren.

Algorithmus

Schritt 1 − Initialisieren Sie „maxSum“ mit 0 und der Prioritätswarteschlange, um das Elementpaar und die Anzahl seiner Vorkommen zu speichern.

Schritt 2− Fügen Sie für alle Array-Elemente {nums[p], 1} Paare in die Warteschlange ein.

Schritt 3 − Fügen Sie dann das Paar {y[p], x[p]} in die Prioritätswarteschlange ein.

Schritt 4− Iterieren, bis n größer als 0 ist.

Schritt 4.1 − Entfernen Sie das erste Element aus der Prioritätswarteschlange.

Schritt 4.2 − Addiere first_ele * max(n, second_ele) zur Summe. Hier verwenden wir max(n, second_ele), um den letzten Fall zu behandeln.

Schritt 4.3 − Subtrahiere second_ele von n.

Schritt 5− Geben Sie maxSum zurück.

Beispiel

#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;
}

Ausgabe

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

Zeitkomplexität – O(N*logN + m*logm), wobei O(N) und O(m) zum Durchlaufen des angegebenen Arrays und O(logN) zum Einfügen und Löschen von Elementen in der Warteschlange verwendet werden.

Raumkomplexität – O(N+M) zum Speichern von Paaren in einer Warteschlange.

Bei der ersten Methode müssen wir das Array in jeder Iteration sortieren, um die kleinsten x[p]-Elemente zu finden. Verwenden Sie eine Prioritätswarteschlange, um Elemente beim Einfügen oder Entfernen automatisch zu sortieren, da sie die Heap-Datenstruktur verwendet. Dadurch wird die Leistung Ihres Codes verbessert.

Das obige ist der detaillierte Inhalt vonMaximal mögliche Array-Summe nach Ausführung der angegebenen Operation. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!