比格设计网站官网,做羞羞的事网站,上海装修公司排名10大家装公司,江桥做网站题干#xff1a;
H君喜欢在阳台晒太阳#xff0c;闲暇之余他会玩一些塔防小游戏。
H君玩的小游戏可以抽象成一棵 nn 个节点的有根树#xff0c;树以 11 为根#xff0c;每个点的深度定义为其到根的简单路径上的点数#xff08;根的深度为 11#xff09;。
H君有 nn 个…题干
H君喜欢在阳台晒太阳闲暇之余他会玩一些塔防小游戏。
H君玩的小游戏可以抽象成一棵 nn 个节点的有根树树以 11 为根每个点的深度定义为其到根的简单路径上的点数根的深度为 11。
H君有 nn 个干员H君会按照某种顺序把她们部署到树的每一个节点上使得每个节点上恰好有一个干员。由于游戏的机制他们对每个节点 ii 都给出了个限制参数 a_iai 要求H君在第 ii 个节点部署干员之前所有深度 a_iai 的节点上不能有干员。同时游戏为了让玩家过关保证了 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_icidi 且对于所有 1 \le j i1≤ji 的 jj 都有 c_j d_jcjdj 。
输入描述
第一行一个数 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代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includestack
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define FF first
#define SS second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,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;}
vectorint 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; iup; i) {int v vv[cur][i];if(v ! fa) dfs(v,cur);}
}
int vis[MAX];
int main()
{cinn;for(int u,v,i 1; in-1; i) {scanf(%d%d,u,v);vv[u].pb(v);vv[v].pb(u);}for(int i 1; in; i) scanf(%d,R[i].a),R[i].id i,D[i].id i;dfs(1,0); sort(R1,Rn1,cmp); sort(D1,Dn1,cmp);priority_queueint,vectorint,greaterint pq;int cur 1;for(int i 1; in; 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()
{cinn;for(int u,v,i 1; in-1; i) {scanf(%d%d,u,v);vv[u].pb(v);vv[v].pb(u);}for(int i 1; in; i) scanf(%d,R[i].a),R[i].id i,D[i].id i;dfs(1,0); sort(R1,Rn1,cmp); sort(D1,Dn1,cmp);priority_queueint,vectorint,greaterint pq;int cur 1;for(int i 1; in; 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()
{cinn;for(int u,v,i 1; in-1; i) {scanf(%d%d,u,v);vv[u].pb(v);vv[v].pb(u);}for(int i 1; in; i) scanf(%d,R[i].a),R[i].id i,D[i].id i;dfs(1,0); sort(R1,Rn1,cmp); sort(D1,Dn1,cmp);priority_queueint,vectorint,greaterint pq;int cur 1;for(int i 1; in; 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()
{cinn;for(int u,v,i 1; in-1; i) {scanf(%d%d,u,v);vv[u].pb(v);vv[v].pb(u);}for(int i 1; in; i) scanf(%d,R[i].a),R[i].id i,D[i].id i;dfs(1,0); sort(R1,Rn1,cmp); sort(D1,Dn1,cmp);priority_queueint,vectorint,greaterint pq;int cur 1;for(int i 1; in; 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 ;
}
