Inhaltsverzeichnis
Beispiel Beispiel
Methode 2
Algorithmus
Beispiel
Ausgabe
Heim Backend-Entwicklung C++ Maximal mögliche Array-Summe nach Ausführung der angegebenen Operation

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

Aug 28, 2023 pm 01:17 PM
操作 最大 数组和

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};
Nach dem Login kopieren

Ausgabe

708
Nach dem Login kopieren

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};
Nach dem Login kopieren

Ausgabe

230
Nach dem Login kopieren

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};
Nach dem Login kopieren

Ausgabe

500
Nach dem Login kopieren

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;
}
Nach dem Login kopieren

Ausgabe

The maximum sum we can get by replacing the array values is 708
Nach dem Login kopieren
Nach dem Login kopieren

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;
}
Nach dem Login kopieren

Ausgabe

The maximum sum we can get by replacing the array values is 708
Nach dem Login kopieren
Nach dem Login kopieren

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!

Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

AI Hentai Generator

AI Hentai Generator

Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

R.E.P.O. Energiekristalle erklärten und was sie tun (gelber Kristall)
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Beste grafische Einstellungen
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. So reparieren Sie Audio, wenn Sie niemanden hören können
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
WWE 2K25: Wie man alles in Myrise freischaltet
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌

Heiße Werkzeuge

Notepad++7.3.1

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6

Dreamweaver CS6

Visuelle Webentwicklungstools

SublimeText3 Mac-Version

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Tutorial zur PyCharm-Nutzung: Führt Sie ausführlich durch die Ausführung des Vorgangs Tutorial zur PyCharm-Nutzung: Führt Sie ausführlich durch die Ausführung des Vorgangs Feb 26, 2024 pm 05:51 PM

PyCharm ist eine sehr beliebte integrierte Entwicklungsumgebung (IDE) für Python. Sie bietet eine Fülle von Funktionen und Tools, um die Python-Entwicklung effizienter und komfortabler zu gestalten. Dieser Artikel führt Sie in die grundlegenden Betriebsmethoden von PyCharm ein und stellt spezifische Codebeispiele bereit, um den Lesern einen schnellen Einstieg zu erleichtern und sich mit der Bedienung des Tools vertraut zu machen. 1. Laden Sie PyCharm herunter und installieren Sie es. Zuerst müssen wir zur offiziellen Website von PyCharm gehen (https://www.jetbrains.com/pyc).

Was ist Sudo und warum ist es wichtig? Was ist Sudo und warum ist es wichtig? Feb 21, 2024 pm 07:01 PM

sudo (Superuser-Ausführung) ist ein Schlüsselbefehl in Linux- und Unix-Systemen, der es normalen Benutzern ermöglicht, bestimmte Befehle mit Root-Rechten auszuführen. Die Funktion von sudo spiegelt sich hauptsächlich in den folgenden Aspekten wider: Bereitstellung von Berechtigungskontrolle: sudo erreicht eine strikte Kontrolle über Systemressourcen und sensible Vorgänge, indem es Benutzern erlaubt, vorübergehend Superuser-Berechtigungen zu erhalten. Normale Benutzer können über sudo bei Bedarf nur vorübergehende Berechtigungen erhalten und müssen sich nicht ständig als Superuser anmelden. Verbesserte Sicherheit: Durch die Verwendung von sudo können Sie die Verwendung des Root-Kontos bei Routinevorgängen vermeiden. Die Verwendung des Root-Kontos für alle Vorgänge kann zu unerwarteten Systemschäden führen, da für jeden fehlerhaften oder nachlässigen Vorgang die vollen Berechtigungen gewährt werden. Und

Schritte und Vorsichtsmaßnahmen für die Linux-Bereitstellung Schritte und Vorsichtsmaßnahmen für die Linux-Bereitstellung Mar 14, 2024 pm 03:03 PM

Betriebsschritte und Vorsichtsmaßnahmen für LinuxDeploy LinuxDeploy ist ein leistungsstarkes Tool, mit dem Benutzer schnell verschiedene Linux-Distributionen auf Android-Geräten bereitstellen können, sodass Benutzer ein vollständiges Linux-System auf ihren Mobilgeräten erleben können. In diesem Artikel werden die Betriebsschritte und Vorsichtsmaßnahmen von LinuxDeploy ausführlich vorgestellt und spezifische Codebeispiele bereitgestellt, um den Lesern zu helfen, dieses Tool besser zu nutzen. Arbeitsschritte: LinuxDeploy installieren: Zuerst installieren

Was tun, wenn Sie vergessen, F2 für das Win10-Startkennwort zu drücken? Was tun, wenn Sie vergessen, F2 für das Win10-Startkennwort zu drücken? Feb 28, 2024 am 08:31 AM

Vermutlich haben viele Benutzer zu Hause mehrere ungenutzte Computer und haben das Einschaltpasswort völlig vergessen, weil sie längere Zeit nicht benutzt wurden. Sie möchten also wissen, was zu tun ist, wenn sie das Passwort vergessen? Dann lasst uns gemeinsam einen Blick darauf werfen. Was tun, wenn Sie vergessen, F2 für das Win10-Startkennwort zu drücken? 1. Drücken Sie den Netzschalter des Computers und drücken Sie dann beim Booten F2 (verschiedene Computermarken haben unterschiedliche Tasten zum Aufrufen des BIOS). 2. Suchen Sie in der BIOS-Schnittstelle nach der Sicherheitsoption (der Speicherort kann je nach Computermarke unterschiedlich sein). Normalerweise im Einstellungsmenü oben. 3. Suchen Sie dann die Option „SupervisorPassword“ und klicken Sie darauf. 4. Zu diesem Zeitpunkt kann der Benutzer sein Passwort sehen und gleichzeitig die Option „Aktiviert“ daneben finden und auf „Dis“ umstellen.

So deaktivieren Sie die Aktionstaste auf dem iPhone 15 Pro und 15 Pro Max So deaktivieren Sie die Aktionstaste auf dem iPhone 15 Pro und 15 Pro Max Nov 07, 2023 am 11:17 AM

Apple brachte einige Pro-exklusive Hardwarefunktionen in das iPhone 15 Pro und 15 Pro Max ein, die die Aufmerksamkeit aller auf sich zogen. Wir sprechen von Titanrahmen, schlanken Designs, dem neuen A17 Pro-Chipsatz, einem aufregenden 5-fach-Teleobjektiv und mehr. Von all dem Schnickschnack, der den iPhone 15 Pro-Modellen hinzugefügt wurde, bleibt die Aktionstaste ein herausragendes und hervorstechendes Merkmal. Es versteht sich von selbst, dass es eine nützliche Ergänzung zum Starten von Aktionen auf Ihrem iPhone ist. Allerdings könnten Sie versehentlich die Aktionstaste gedrückt halten und die Funktion unbeabsichtigt auslösen. Ehrlich gesagt ist es ärgerlich. Um dies zu vermeiden, sollten Sie die Aktionstaste auf dem iPhone 15 Pro und 15 Pro Max deaktivieren. lassen

Huawei Mate60 Pro Screenshot-Bedienschritte teilen Huawei Mate60 Pro Screenshot-Bedienschritte teilen Mar 23, 2024 am 11:15 AM

Mit der Beliebtheit von Smartphones ist die Screenshot-Funktion zu einer der wesentlichen Fähigkeiten für die tägliche Nutzung von Mobiltelefonen geworden. Als eines der Flaggschiff-Handys von Huawei hat die Screenshot-Funktion des Huawei Mate60Pro natürlich große Aufmerksamkeit bei den Nutzern auf sich gezogen. Heute werden wir die Screenshot-Bedienungsschritte des Huawei Mate60Pro-Mobiltelefons teilen, damit jeder bequemer Screenshots machen kann. Erstens bietet das Huawei Mate60Pro-Mobiltelefon eine Vielzahl von Screenshot-Methoden, und Sie können die Methode auswählen, die Ihren persönlichen Gewohnheiten entspricht. Im Folgenden finden Sie eine detaillierte Einführung in mehrere häufig verwendete Abfangfunktionen:

Benutzerdefinierte Aktionsschaltflächen: Entdecken Sie die Personalisierung auf dem iPhone 15 Pro Benutzerdefinierte Aktionsschaltflächen: Entdecken Sie die Personalisierung auf dem iPhone 15 Pro Sep 24, 2023 pm 03:05 PM

Apples iPhone 15 Pro und iPhone 15 Pro Max führen eine neue programmierbare Aktionstaste ein, die den herkömmlichen Klingel-/Stummschalter über den Lautstärketasten ersetzt. Lesen Sie weiter, um zu erfahren, was die Aktionsschaltfläche bewirkt und wie Sie sie anpassen können. Eine neue Aktionstaste bei Apple iPhone 15 Pro-Modellen ersetzt den herkömmlichen iPhone-Schalter, der Klingeln und Lautlos aktiviert. Standardmäßig aktiviert die neue Taste weiterhin beide Funktionen durch langes Drücken, aber Sie können durch langes Drücken auch eine Reihe anderer Funktionen ausführen, darunter Schnellzugriff auf die Kamera oder Taschenlampe, die Aktivierung von Sprachnotizen, den Fokusmodus, die Übersetzung usw Barrierefreiheitsfunktionen wie eine Lupe. Sie können es auch mit einer einzigen Verknüpfung verknüpfen, was eine Menge weiterer Möglichkeiten eröffnet

CSS-Webseiten-Scroll-Überwachung: Überwachen Sie das Scrollen von Webseiten und führen Sie entsprechende Vorgänge aus CSS-Webseiten-Scroll-Überwachung: Überwachen Sie das Scrollen von Webseiten und führen Sie entsprechende Vorgänge aus Nov 18, 2023 am 10:35 AM

CSS-Webseiten-Scroll-Überwachung: Überwachen Sie das Scrollen von Webseiten und führen Sie entsprechende Vorgänge aus. Mit der kontinuierlichen Entwicklung der Front-End-Technologie werden die Effekte und Interaktionen von Webseiten immer vielfältiger. Unter diesen ist die Scroll-Überwachung eine gängige Technologie, mit der einige Spezialeffekte oder Vorgänge basierend auf der Scroll-Position ausgeführt werden können, wenn der Benutzer auf der Webseite scrollt. Im Allgemeinen kann die Scroll-Überwachung über JavaScript implementiert werden. In einigen Fällen können wir den Effekt der Scroll-Überwachung jedoch auch durch reines CSS erzielen. In diesem Artikel wird erläutert, wie das Scrollen von Webseiten über CSS implementiert wird

See all articles