題意 ：

• 類似于堆棧的火車站。給出長為$2n$的括號序列，（）分別代表放入火車站和推出火車站，又給了n輛火車的顏色。
• 求構造一個關于顏色的放入序列，滿足不存在同一放入火車的時刻在火車站內顏色的序列相同。

思路 ：

• 將棧操作看作樹，要求轉化為給每一個節點染色，使得從根到每一個節點的鏈所構成的顏色序列兩兩不同。注意到兩個都在第i層的節點，如果它們父親不同，則從根到它們父親的鏈所構成的顏色序列不同，這使得根到它們所構成的顏色序列也一定不同。
• 因此，問題轉化為，每個點的k個兒子顏色互不相同，對于一個節點，假設有k個兒子，我們選取剩余火車數最多的k個顏色對應上去即可（使用優先隊列實現）。

如下圖，

會發現在第一行和第二行的條件（顏色不同）滿足后，第三行的條件（大于一個數的顏色不同）自然會滿足，因此想到樹的性質，即讓父節點的每個兒子顏色互不相同。

#include <iostream> #include <algorithm> #include <cmath> #include <cstring> #include <string> #include <vector> #include <unordered_map> #include <unordered_set> #include <set> #include <map> #include <stack> #include <queue> #include <deque> #define endl '\n' #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define lowbit(x) (x&-x) using namespace std; const double pi = acos(-1); typedef long long ll; typedef pair<int, int> PII; typedef pair<long, long> PLL;const int N = 1e6 + 10;vector<int> G[N]; int pa[N], tot = 0; int a[N]; // 顏色i的數量 int ans[N]; // 火車序列為i的火車顏色int main() {IOS;int n;string s;cin >> n >> s;// 建樹int p = 0;for (auto ch : s)if (ch == '('){G[p].push_back( ++ tot);pa[tot] = p;p = tot;}elsep = pa[p];for (int i = 1; i <= n; i ++ ){int x;cin >> x;a[x] ++ ;}// 默認是大頂堆priority_queue<PII> pq; // 對應顏色的個數，每種顏色for (int i = 1; i <= n; i ++ )pq.push({a[i], i});// 枚舉每個點for (int i = 0; i <= tot; i ++ ){vector<PII> ve; // 備份// 節點i的每個兒子for (int j = 0; j < G[i].size(); j ++ ){auto p = pq.top(); pq.pop();if (p.first == 0){cout << "NO" << endl;return 0;}ans[G[i][j]] = p.second;p.first -- ;ve.push_back(p);}for (auto p : ve)pq.push(p);}cout << "YES" << endl;for (int i = 1; i <= n; i ++ ) cout << ans[i] << " ";cout << endl;return 0; }

總結

以上是生活随笔為你收集整理的Train Wreck 模拟-建树-优先队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。