Heim > Backend-Entwicklung > C++ > C++-Programm zum Überprüfen, ob zwei Briefstapel gelöscht werden können

C++-Programm zum Überprüfen, ob zwei Briefstapel gelöscht werden können

PHPz
Freigeben: 2023-09-04 14:01:06
nach vorne
1143 Leute haben es durchsucht

C++-Programm zum Überprüfen, ob zwei Briefstapel gelöscht werden können

Angenommen, es gibt 2n Buchstaben, auf jedem Buchstaben steht eine ganze Zahl zwischen 1 und n. Auf ihnen stehen zwei Buchstaben mit der gleichen Nummer. Diese Buchstaben werden in m Stapel unterteilt, und auf dem i-ten Stapel befindet sich ein Stapel [i] Buchstabe. Unsere Aufgabe besteht darin, alle Stapel auf folgende Weise zu leeren:

  • Wir müssen zwei beliebige Stapel auswählen und die obersten Buchstaben von beiden Stapeln entfernen.

  • Die von uns entfernten Buchstaben müssen die gleiche Nummer haben.

Wenn wir den M-Heap auf diese Weise löschen können, geben Sie true aus, andernfalls geben Sie false zurück.

Wenn also die Eingabe n = 3, m = 2, Stapel = {{2, 1, 3}, {2, 1, 3}} ist, dann ist die Ausgabe wahr.

Es gibt zwei Stapel und auf den Buchstaben jedes Stapels stehen die Zahlen 2, 1 und 3. Wir können also Briefe von beiden Stapeln entfernen und sie auf die angegebene Weise leeren.

Um dieses Problem zu lösen, werden wir die folgenden Schritte ausführen:

Define one 2D array dp
Define an array tvec
for initialize i := 0, when i < m, update (increase i by 1), do:
   k := size of stacks[i]
   for initialize j := 0, when j < k, update (increase j by 1), do:
      if j < 0, then:
         insert p at the end of dp[stacks[i, j]]
         (increase tvec[p] by 1)
      p := stacks[i, j]
Define an array tp
for initialize i := 1, when i <= n, update (increase i by 1), do:
   Define one queue q
   insert i into q
   while (q is not empty), do:
    if not tp[first element of q] and tvec[first element of q] is same as 0, then:
         for each element next in dp[first element of q], do:
             (decrease tvec[next] by 1)
             insert next into q
         tp[first element of q] := true
   delete first element from q
for initialize i := 1, when i <= n, update (increase i by 1), do:
   if tvec[i] is not equal to 0, then:
return false
return true
Nach dem Login kopieren

Beispiel

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

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

bool solve(int n, int m, vector<vector<int>> stacks){
   vector<vector<int>> dp(n + 1);
   vector<int> tvec(n + 1);
   for(int i = 0; i < m; i++){
      int k = stacks[i].size();
      int p;
      for(int j = 0; j < k; j++){
         if(j > 0){
            dp[stacks[i][j]].push_back(p);
            tvec[p]++;
         }
         p = stacks[i][j];
      }
   }
   vector<bool> tp(n + 1);
   for(int i = 1; i <= n; i++){
      queue<int> q;
      q.push(i);
      while(!q.empty()){
         if(!tp[q.front()] && tvec[q.front()] == 0){
            for(auto next: dp[q.front()]){
               tvec[next]--;
               q.push(next);
            }
            tp[q.front()]=true;
         }
         q.pop();
      }
   }
   for(int i = 1; i <= n; i++){
      if(tvec[i] != 0){
         return false;
      }
   }
   return true;
}
int main() {
   int n = 3, m = 2;
   vector<vector<int>> stacks = {{2, 1, 3}, {2, 1, 3}};
   cout<< solve(n, m, stacks);
   return 0;
}
Nach dem Login kopieren

Eingabe

3, 2, {{2, 1, 3}, {2, 1, 3}}
Nach dem Login kopieren

Ausgabe

1
Nach dem Login kopieren

Das obige ist der detaillierte Inhalt vonC++-Programm zum Überprüfen, ob zwei Briefstapel gelöscht werden können. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Verwandte Etiketten:
Quelle:tutorialspoint.com
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
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage