題干：

H君喜歡在陽臺曬太陽，閑暇之余他會玩一些塔防小游戲。

H君玩的小游戲可以抽象成一棵?nn?個節點的有根樹，樹以?11?為根，每個點的深度定義為其到根的簡單路徑上的點數（根的深度為?11）。

H君有?nn?個干員，H君會按照某種順序把她們部署到樹的每一個節點上，使得每個節點上恰好有一個干員。由于游戲的機制，他們對每個節點?ii?都給出了個限制參數?a_iai??，要求H君在第?ii?個節點部署干員之前，所有深度?> a_i>ai??的節點上不能有干員。同時游戲為了讓玩家過關，保證了?a_iai??大于等于點?ii?的深度。

H君將每一次部署干員的節點按順序寫在紙上，形成了一個?1 \dots n1…n?的排列，H君為了獲得更多的獎勵，想要最小化這個排列的字典序。

我們認為排列?c_1,c_2..c_nc1?,c2?..cn??的字典序比排列?d_1,d_2..d_nd1?,d2?..dn??的字典序小，當且僅當?c, dc,d?不完全相同且存在一個下標?ii，滿足?c_i < d_ici?<di??且對于所有?1 \le j < i1≤j<i?的?jj?都有?c_j = d_jcj?=dj??。

輸入描述

第一行一個數?nn?。

接下來?n - 1n?1?行，每行兩個數?x, yx,y?表示樹上的一條邊 。

最后一行?nn?個數，表示?a_iai??。

數據范圍：

1\le n \le 5 \times 10^5, 1 \le a_i \le n1≤n≤5×105,1≤ai?≤n。

輸出描述

第一行?nn?個數，表示字典序最小的排列。

樣例輸入 1?

5 1 5 5 3 1 4 4 2 1 3 3 3 2

樣例輸出 1

1 4 5 2 3

樣例輸入 2?

10 1 7 7 8 7 2 8 9 7 6 2 4 9 5 8 10 6 3 5 3 4 4 5 3 5 3 5 4

樣例輸出 2

1 2 6 7 8 3 4 9 10 5

解題報告：

考慮貪心的策略。首先根據給定的a數組排序，因為這樣的話，是限制逐步增加的情況，同時可選擇的元素逐步增多，所以可以考慮同時用優先隊列動態維護可以“寫在紙上”的元素。

按照這個想法，我們可以一個一個構造。首先肯定是深度小于在排好序后最小的a的那些點都可以“寫在紙上”，我們把可以“寫在紙上”的候選點都放到優先隊列中。考慮什么時候可以擴展優先隊列中的元素呢？也就是你把第i號點寫在紙上了之后，才能有更多候選點，所以每次擴展之后就把優先隊列中所有 編號小于第i號點的編號 的那些點都“寫在紙上”。然后重復上述操作就好。這也是為什么要求字典序最小，因為這樣就可以使得所有候選點中標號小于i的編號的那些點，可以優先擴展出來，比先擴展i編號的節點更優。

其實這題的核心就是用優先隊列動態維護可以“寫在紙上”的候選點，優先級是編號最小。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 5e5 + 5; int n,a[MAX]; struct Node {int a,id; } R[MAX],D[MAX]; bool cmp(Node a,Node b) {return a.a != b.a ? a.a < b.a : a.id < b.id;} vector<int> vv[MAX],ans; void dfs(int cur,int fa) {D[cur].a = D[fa].a + 1;int up = vv[cur].size();for(int i = 0; i<up; i++) {int v = vv[cur][i];if(v != fa) dfs(v,cur);} } int vis[MAX]; int main() {cin>>n;for(int u,v,i = 1; i<=n-1; i++) {scanf("%d%d",&u,&v);vv[u].pb(v);vv[v].pb(u);}for(int i = 1; i<=n; i++) scanf("%d",&R[i].a),R[i].id = i,D[i].id = i;dfs(1,0); sort(R+1,R+n+1,cmp); sort(D+1,D+n+1,cmp);priority_queue<int,vector<int>,greater<int> > pq;int cur = 1;for(int i = 1; i<=n; i++) {if(vis[R[i].id]) continue;while(D[cur].a <= R[i].a && cur <= n) {pq.push(D[cur].id);cur++;}while(pq.size() && pq.top() <= R[i].id) ans.pb(pq.top()),vis[pq.top()] = 1,pq.pop();}for(int x : ans) {printf("%d ",x);}return 0 ; }

錯誤代碼1：

錯誤原因，剛開始就是這樣寫的，想法就是找到最小的a的那個編號id（假設此時決策的id是idd），所有深度小于等于idd的都先“寫到紙上”。但是其實是不對的，因為你需要看的是編號也小于idd的。因為編號如果大于idd的話那肯定要先寫idd，但是寫idd的話就會解鎖這一層封印，所以寫完idd之后下一個寫的不一定是此時候選點中編號大于idd的那些點，也有可能是解除封印后又有編號更小的點了；而編號小于idd的可以直接寫到紙上，因為你是按a排序的，所以不需要擔心寫idd之后會解鎖新東西。因為就算是解鎖新東西了也不能加入到候選點中，因為idd還沒有寫，所以無法解封那些。

int main() {cin>>n;for(int u,v,i = 1; i<=n-1; i++) {scanf("%d%d",&u,&v);vv[u].pb(v);vv[v].pb(u);}for(int i = 1; i<=n; i++) scanf("%d",&R[i].a),R[i].id = i,D[i].id = i;dfs(1,0); sort(R+1,R+n+1,cmp); sort(D+1,D+n+1,cmp);priority_queue<int,vector<int>,greater<int> > pq;int cur = 1;for(int i = 1; i<=n; i++) {while(D[cur].a <= R[i].a && cur <= n) {pq.push(D[cur].id);cur++;}while(pq.size()) ans.pb(pq.top()),pq.pop();} for(int x : ans) {printf("%d ",x);}return 0 ; }

錯誤代碼2：

因為其實你vis數組不是用來在輸出的時候去重用的，而是用來看省去下面的判斷的。

int vis[MAX]; int main() {cin>>n;for(int u,v,i = 1; i<=n-1; i++) {scanf("%d%d",&u,&v);vv[u].pb(v);vv[v].pb(u);}for(int i = 1; i<=n; i++) scanf("%d",&R[i].a),R[i].id = i,D[i].id = i;dfs(1,0); sort(R+1,R+n+1,cmp); sort(D+1,D+n+1,cmp);priority_queue<int,vector<int>,greater<int> > pq;int cur = 1;for(int i = 1; i<=n; i++) { // if(vis[R[i].id]) continue;while(D[cur].a <= R[i].a && cur <= n) {pq.push(D[cur].id);cur++;}while(pq.size() && pq.top() <= R[i].id) ans.pb(pq.top()),pq.pop();}for(int x : ans) {if(vis[x]) continue;printf("%d ",x);vis[x] = 1;}return 0 ; }

改成這樣就可以AC了：

int main() {cin>>n;for(int u,v,i = 1; i<=n-1; i++) {scanf("%d%d",&u,&v);vv[u].pb(v);vv[v].pb(u);}for(int i = 1; i<=n; i++) scanf("%d",&R[i].a),R[i].id = i,D[i].id = i;dfs(1,0); sort(R+1,R+n+1,cmp); sort(D+1,D+n+1,cmp);priority_queue<int,vector<int>,greater<int> > pq;int cur = 1;for(int i = 1; i<=n; i++) { // if(vis[R[i].id]) continue;while(D[cur].a <= R[i].a && cur <= n) {pq.push(D[cur].id);cur++;}if(vis[R[i].id]) continue;while(pq.size() && pq.top() <= R[i].id) ans.pb(pq.top()),vis[pq.top()] = 1,pq.pop();}for(int x : ans) {printf("%d ",x);}return 0 ; }

?

總結

以上是生活随笔為你收集整理的【Comet OJ - Contest #5 - C】迫真小游戏（优先队列，贪心构造，树，字典序）的全部內容，希望文章能夠幫你解決所遇到的問題。

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