题目&＃xff1a;https://www.luogu.org/problemnew/show/P4364
原来想了一个错误的思路&＃xff0c;就是这样&＃xff1a;
solve( cr , l , r ) 表示 cr 为根的子树填 [ l , r ] 的数&＃xff1b;然后把 l 给 cr &＃xff0c;剩下的 [ l&＃43;1 , r ] 分成一段一段&＃xff0c;大的段给标号小的孩子。
然后只能得 60 分。
#include
#include
#include
#include
#include
#define db double
#define pb push_back
using namespace std;
int rdn()
{int ret&＃61;0;bool fx&＃61;1;char ch&＃61;getchar();while(ch>&＃39;9&＃39;||ch<&＃39;0&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)fx&＃61;0;ch&＃61;getchar();}while(ch>&＃61;&＃39;0&＃39;&&ch<&＃61;&＃39;9&＃39;)ret&＃61;ret*10&＃43;ch-&＃39;0&＃39;,ch&＃61;getchar();return fx?ret:-ret;
}
const int N&＃61;5e5&＃43;5;
int n,d[N],p[N],siz[N]; db k;
vector<int> vt[N];
void dfs(int cr)
{siz[cr]&＃61;1;for(int i&＃61;0,lm&＃61;vt[cr].size();i
}
void solve(int cr,int l,int r)
{p[cr]&＃61;d[l]; int p0&＃61;l;for(int i&＃61;vt[cr].size()-1;i>&＃61;0;i--){solve(vt[cr][i],p0&＃43;1,p0&＃43;siz[vt[cr][i]]);p0&＃43;&＃61;siz[vt[cr][i]];}
}
int main()
{n&＃61;rdn();scanf("%lf",&k);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)d[i]&＃61;rdn();sort(d&＃43;1,d&＃43;n&＃43;1);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)vt[(int)floor(i/k)].pb(i);dfs(0); solve(0,0,n);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)printf("%d ",p[i]);puts(""); return 0;
}
看了看题解。https://files-cdn.cnblogs.com/files/NaVi-Awson/IIIDX.pdf
关于 “去掉父亲预留的影响” &＃xff0c;是这样考虑&＃xff1a;
按顺序枚举节点&＃xff0c;在树上就是像 bfs 一样遍历&＃xff1b;
一个点 cr 要预留&＃xff0c;是为了让 “和它深度相同的点” 不要抢了它的位置。
当开始遍历 cr 的子树的时候&＃xff0c;直接去掉 cr 的影响并再也不加入了&＃xff1b;这样不会有错&＃xff0c;因为此时不会再遍历和 cr 深度相同的点了&＃xff1b;
下一层的点已经由它们的父亲留好了位置&＃xff0c;所以去掉 cr 的影响也不会让之后的点出错。
还有一种不太能理解的做法&＃xff1a;https://www.cnblogs.com/HocRiser/p/8742680.html
#include
#include
#include
#include
#include
#define ls Ls[cr]
#define rs Rs[cr]
using namespace std;
int rdn()
{int ret&＃61;0;bool fx&＃61;1;char ch&＃61;getchar();while(ch>&＃39;9&＃39;||ch<&＃39;0&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)fx&＃61;0;ch&＃61;getchar();}while(ch>&＃61;&＃39;0&＃39;&&ch<&＃61;&＃39;9&＃39;)ret&＃61;ret*10&＃43;ch-&＃39;0&＃39;,ch&＃61;getchar();return fx?ret:-ret;
}
int Mn(int a,int b){return a
int Mx(int a,int b){return a>b?a:b;}
const int N&＃61;5e5&＃43;5,M&＃61;N<<1;
int n,a[N],fa[N],ans[N],siz[N],tp[N],tx[N];
int tot,Ls[M],Rs[M],mn[M],tg[M];
void pshp(int cr){mn[cr]&＃61;Mn(mn[ls],mn[rs]);}
void build(int l,int r,int cr)
{if(l&＃61;&＃61;r){mn[cr]&＃61;n-l;return;}int mid&＃61;l&＃43;r>>1;ls&＃61;&＃43;&＃43;tot; build(l,mid,ls);rs&＃61;&＃43;&＃43;tot; build(mid&＃43;1,r,rs);pshp(cr);
}
void pshd(int cr)
{if(!tg[cr])return; int w&＃61;tg[cr]; tg[cr]&＃61;0;tg[ls]&＃43;&＃61;w; tg[rs]&＃43;&＃61;w; mn[ls]&＃43;&＃61;w; mn[rs]&＃43;&＃61;w;
}
void mdfy(int l,int r,int cr,int L,int R,int k)
{if(l>&＃61;L&&r<&＃61;R){tg[cr]&＃43;&＃61;k;mn[cr]&＃43;&＃61;k;return;}int mid&＃61;l&＃43;r>>1; pshd(cr);if(L<&＃61;mid)mdfy(l,mid,ls,L,R,k);if(mid
}
int qry(int l,int r,int cr,int k)
{if(l&＃61;&＃61;r)return mn[cr]>&＃61;k?l:-1;int mid&＃61;l&＃43;r>>1,ret&＃61;-1; pshd(cr);if(mn[ls]>&＃61;k)ret&＃61;qry(mid&＃43;1,r,rs,k);if(ret>&＃61;0)return ret;return qry(l,mid,ls,k);
}
int main()
{n&＃61;rdn(); double sl; scanf("%lf",&sl);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)a[i]&＃61;rdn();sort(a&＃43;1,a&＃43;n&＃43;1);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)tp[i]&＃61;a[i];int m&＃61;unique(tp&＃43;1,tp&＃43;n&＃43;1)-tp-1;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){a[i]&＃61;lower_bound(tp&＃43;1,tp&＃43;m&＃43;1,a[i])-tp;tx[a[i]]&＃43;&＃43;;}for(int i&＃61;2;i<&＃61;m;i&＃43;&＃43;)tx[i]&＃43;&＃61;tx[i-1];for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) fa[i]&＃61;floor(i/sl);for(int i&＃61;n;i;i--) siz[i]&＃43;&＃43;,siz[fa[i]]&＃43;&＃61;siz[i];tot&＃61;1; build(0,n,1);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){if(i>1&&fa[i]!&＃61;fa[i-1])mdfy(0,n,1,0,ans[fa[i]]-1,siz[fa[i]]-1);//-1 for already useint p&＃61;qry(0,n,1,siz[i])&＃43;1;p&＃61;&＃43;&＃43;tx[a[p]-1];//
ans[i]&＃61;p;mdfy(0,n,1,0,p-1,-siz[i]);}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)printf("%d ",tp[a[ans[i]]]);puts(""); return 0;
}
京公网安备 11010802041100号