C++-Programm: Zählen Sie die Anzahl der Operationen, die erforderlich sind, um alle Geschenke in der Menge gleich zu machen

Angenommen, wir haben zwei Arrays A und B, jeweils der Größe n. Es gibt n Geschenke und wir möchten sie einigen Kindern schenken. Das i-te Geschenk besteht aus A[i]-Bonbons und B[i]-Orangen. Während eines Umzugs können wir einige Geschenke auswählen und eine der folgenden Aktionen ausführen:

• eine Süßigkeit aus diesem Geschenk herausnehmen (falls vorhanden); p>

• eine Orange aus diesem Geschenk herausnehmen (falls vorhanden);

• Nehmen Sie aus diesem Geschenk (falls vorhanden) eine Süßigkeit und ein orangefarbenes Geschenk heraus.

Alle Geschenke sollten gleich sein. Das bedeutet, dass nach einer Reihe von Zügen die folgenden zwei folgen Die Bedingungen sollten erfüllt sein: A[0] = A[1] = ... = A[n-1] und B[0] = B[1] = ... = B[n-1]. wir müssen Finden Sie die Mindestanzahl an Schritten, die erforderlich sind, um alle gegebenen Geschenke gleich zu machen.

Problemkategorie

Die oben genannten Probleme können durch die Anwendung gieriger Problemlösungstechniken gelöst werden. Die Greedy-Algorithmus-Technologie ist die Art von Algorithmus, die derzeit die beste Lösung bietet Wählen Sie, anstatt alle möglichen Lösungen auszuprobieren. Auch die Greedy-Algorithmus-Technologie Wird zur Lösung von Optimierungsproblemen verwendet, genau wie sein großer Bruder, die dynamische Programmierung. Aktiv Beim Programmieren müssen Sie alle möglichen Teilprobleme durchlaufen und das optimale finden Lösung, aber sie hat einen Nachteil; sie erfordert mehr Zeit und Platz. Daher in verschiedenen Die Szenario-Greedy-Technik wird verwendet, um die beste Lösung für das Problem zu finden. Obwohl es wahr ist bietet nicht in allen Situationen die beste Lösung. Bei sorgfältiger Planung kann jedoch schneller eine Lösung erzielt werden Dynamisches Programmierproblem. Greedy-Techniken bieten lokal optimale Lösungen Optimierungsproblem. Beispiele für diese Technik sind Kruskals und Prims Minimaltechnik Spanning Tree (MST)-Algorithmus, Huffman-Tree-Codierung, Dijkstras Single-Source-Shortest-Path Fragen etc = [3, 5, 6]; B = [3, 2, 3], dann ist die Ausgabe 6, Da es ursprünglich von B übernommen wurde, wird B[0] nun zu [2, 2, 3] und dann von A[1] übernommen, also A = [3, 4, 6], dann wieder aus A[1], also A = [3, 3, 6], dann aus A[2] und B[2], also sie nach [3, 3, 5] und [2, 2, 2], dann von A[2] nach A = [3, 3, 4], wieder von A[2] nach Sei es [3, 3, 3]. Jetzt hat A also die gleiche Anzahl an Bonbons und B die gleiche Anzahl an Orangen.

Schritte

Um dieses Problem zu lösen, folgen wir den folgenden Schritten - p>

minA := inf
minB := inf
kq := 0
n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
   minA := minimum of minA and A[i]
for initialize i := 0, when i < n, update (increase i by 1), do:
   minB := minimum of minB and B[i]
for initialize i := 0, when i < n, update (increase i by 1), do:
   kq := kq + maximum of (A[i] - minA) and (B[i] - minB)
return kq

Beispiel

Sehen wir uns zum besseren Verständnis die folgende Implementierung an -

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, vector<int> B){
   int minA = 999, minB = 999, kq = 0;
   int n = A.size();
   for (int i = 0; i < n; i++)
      minA = min(minA, A[i]);
   for (int i = 0; i < n; i++)
      minB = min(minB, B[i]);
   for (int i = 0; i < n; i++)
      kq += max(A[i] - minA, B[i] - minB);
   return kq;
}
int main(){
   vector<int> A = { 3, 5, 6 };
   vector<int> B = { 3, 2, 3 };
   cout << solve(A, B) << endl;
}

Eingabe

{ 3, 5, 6 }, { 3, 2, 3 }

Ausgabe

6

Das obige ist der detaillierte Inhalt vonC++-Programm: Zählen Sie die Anzahl der Operationen, die erforderlich sind, um alle Geschenke in der Menge gleich zu machen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!