Reduzieren Sie ein Array mithilfe der angegebenen, in C++ implementierten Operation auf eine Ganzzahl

Gegeben ist eine ganzzahlige Variable Zahl als Eingabe. Betrachten wir ein Array mit Elementen im Bereich von 1 bis Nummer. Die Reihenfolge der Elemente kann beliebig sein. Wenn wir Nummer-1-Operationen für das Array ausführen, lautet die Operation wie folgt:

• Wir wählen zwei Elemente A und B aus dem Array aus.

• Entfernen A und B aus dem Array.

• Ersetzen Sie A und B Die Summe der Quadrate wird dem Array hinzugefügt

Letztendlich erhalten wir einen einzelnen ganzzahligen Wert. Das Ziel besteht darin, den maximal möglichen Wert für dieses Element zu finden.

Prioritätswarteschlange verwenden

• Um das Endergebnis zu maximieren, müssen wir A und B auswählen, um sie so groß wie möglich zu machen.

• Um die größten A und B zu finden, verwenden wir eine Prioritätswarteschlange, um die darin enthaltenen Elementwerte zu speichern.

• Prioritätswarteschlange speichert Elemente in absteigender Reihenfolge.

• Das oberste Element hat den größten Wert und so weiter. Nachdem wir beide Elemente platziert haben, schieben wir ihre Quadrate erneut in die Warteschlange.

• Lässt die Zahl-1 aufplatzen und drücken, um das gewünschte Ergebnis zu erzielen. ?? die Prioritätswarteschlange: 2 1

A=5, B=4: A

+B

=1+4=5Das letzte Element: 5

Eingabe - Zahl=5

Ausgabe - Einzelnes Element nach Array-Reduzierung: 5

- Angenommen, die Elemente im Array sind [5 1 2 4 3]Nach dem Einfügen in die Prioritätswarteschlange: 5 4 3 2 1A=5 , B=4: A

+B

=25+16=41 : 41 3 2 1A=41, B=3 : A

+B2=1681+9=1690 : 1690 2 1

A=1690, B=2 : A2+B

=1681+4=2856104 : 2856104 1

A=2856104 , B=1 : A²+B² =1187163712+1= 1187163713 : 1187163713

Letztes Element: 1187163713Die im folgenden Programm verwendete Methode ist wie folgtIn dieser Methode legen wir die Prioritätswarteschlange fest, um die Elemente des Arrays in absteigender Reihenfolge zu speichern. Platzieren Sie die beiden größten Elemente und schieben Sie die Summe ihrer Quadrate zurück in die Warteschlange, bis nur noch ein Wert übrig bleibt.

Erhalten Sie die Eingabevariable Nummer.

Setzen Sie den Datentyp des Ergebnisses auf long long integer - lli Die Funktion reduArray(int Num) akzeptiert die eingegebene Zahl und gibt die größte einzelne Ganzzahl zurück, die mit der obigen Operation berechnet wurde.

Verwenden Sie eine Prioritätswarteschlange pQueue.

Verwenden Sie eine While-Schleife, um die Zahlen 1 bis N in pQueue zu füllen.
Wenn i
Jetzt speichert pQueue die Ganzzahlen 1 bis N in absteigender Reihenfolge mit der Größe N.
Verwenden Sie eine While-Schleife, um pQueue zu durchlaufen, bis seine Größe >= 1 ist.
Setzen Sie den Maximalwert auf var1=pQueue.top() und fügen Sie ihn hinzu.
Setzen Sie den nächsten Maximalwert auf var2=pQueue.top() und fügen Sie ihn hinzu.
Setze var1 auf sein Quadrat und var2 auf sein Quadrat.
Var1+var2 erneut in pQueue verschieben.
Am Ende der while-Schleife das oberste Element zurückgeben.
Drucken Sie das Ergebnis in der Hauptfunktion aus.
Beispiel

• #include <bits/stdc++.h>
  using namespace std;
  #define lli long long int
  int reduceArray(int Num){
     priority_queue<lli> pQueue;
     int i=1;
     while(i<=Num){
        pQueue.push(i);
        i=i+1;
     }
     while (pQueue.size() > 1) {
        lli var1 = pQueue.top();
        pQueue.pop();
        lli var2 = pQueue.top();
        pQueue.pop();
        var1=var1*var1;
        var2=var2*var2;
        pQueue.push(var1+var2);
     }
     return pQueue.top();
  }
  int main(){
     int Number = 5;
     cout<<"Single element after array reduction: "<<reduceArray(Number);
     return 0;
  }

  Nach dem Login kopieren

  Ausgabe

Wenn wir den obigen Code ausführen, wird die folgende Ausgabe generiert

• Single element after array reduction: 1187163713

  Nach dem Login kopieren

Das obige ist der detaillierte Inhalt vonReduzieren Sie ein Array mithilfe der angegebenen, in C++ implementierten Operation auf eine Ganzzahl. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!