Andaikan terdapat 2n huruf, setiap huruf mempunyai integer antara 1 dan n tertulis di atasnya. Terdapat dua huruf dengan nombor yang sama ditulis padanya. Huruf-huruf ini dibahagikan kepada longgokan m, dan terdapat huruf timbunan[i] pada longgokan ke-i. Tugas kami ialah mengosongkan semua longgokan dengan cara berikut:
Kita perlu memilih mana-mana dua longgokan dan mengeluarkan huruf atas daripada kedua-dua longgokan.
Huruf yang kita keluarkan mestilah mempunyai nombor yang sama.
Jika kita boleh mengosongkan timbunan m dengan cara ini, cetak benar, jika tidak kembali palsu.
Jadi jika input ialah n = 3, m = 2, tindanan = {{2, 1, 3}, {2, 1, 3}}, maka output akan menjadi benar.
Terdapat dua longgokan, dan nombor 2, 1, dan 3 ditulis pada huruf dalam setiap longgokan. Oleh itu, kita boleh mengeluarkan huruf dari kedua-dua longgokan dan mengosongkannya dengan cara yang diberikan.
Untuk menyelesaikan masalah ini kami akan mengikuti langkah berikut:
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
Mari lihat pelaksanaan berikut untuk pemahaman yang lebih baik -
#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; }
3, 2, {{2, 1, 3}, {2, 1, 3}}
Atas ialah kandungan terperinci Program C++ untuk menyemak sama ada timbunan dua huruf boleh dikosongkan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!