BZOJ2799:[Poi2012]Salaries 贪心
思路:
我们维护以每一个节点为根的子树内部有多少个没有确定权值的点,另外,我们利用一个数组维护每个权值已经给了哪个节点.
我们从小到大遍历每个权值,若这个权值当前并没有确定给哪个节点,则将其压入栈中;否则我们在对应节点的子树中进行一系列确定操作:
我们维护栈中有多少个权值,以及有多少个自由权值.(这个是什么一会再说)
若未确定的节点数正好等于当前的自由权值数与栈中的权值总数,显而易见这些权值都应该分配给这棵子树.但是只有只有一个儿子的情况才能确定这个权值.所以我们不断在链上去找即可.这个过程可能确定了一些权值,随后我们将栈清空,并令自由权值的数目为0.因为他们只能被拘束在这颗子树内,而不能去别的地方.
若不然,我们将自由权值及栈中的权值分配给这棵子树所需要的数目,剩下的全部变成自由权值.
我们发现栈中的权值和自由权值很像,但是为什么不都搞成自由权值,而是非要维护一个栈呢?
这个问题显而易见:自由权值都是可以互相交换的(等价的),而栈中的元素显然不是!
于是\(O(n)\)水.
#include<cstdio>#include<cstring>#include<cctype>#include<iostream>#include<algorithm>#include<vector>using namespace std;namespace Fio{ inline int getc(){ static const int L=1<<15;static char buf[L],*S=buf,*T=buf; if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;} return*S++; } template<typename T>inline void Get(T&x){ int c;while(!isdigit(c=getc()));x=c-'0';while(isdigit(c=getc()))x=(x<<1)+(x<<3)+c-'0'; }}#define N 1000010vector<int>v[N];int pa[N],w[N];int q[N],fr,ta,ins[N],size[N],stk[N],top,tot,sum;int main(){ int n;Fio::Get(n); register int i,j; for(i=1;i<=n;++i){ Fio::Get(pa[i]),Fio::Get(w[i]);if(i==pa[i])w[i]=n; if(w[i])q[ta++]=i,ins[w[i]]=i;else v[pa[i]].push_back(i); } int u; while(fr<ta){ u=q[fr++]; for(j=0;j<v[u].size();++j)q[ta++]=v[u][j]; } for(i=n-1;i>=0;--i){ u=q[i]; size[u]=1; for(j=0;j<v[u].size();++j)size[u]+=size[v[u][j]]; } int tot=0; for(i=1;i<=n;++i){ if(!(u=ins[i])){stk[++top]=i;continue;} int sum=0,ac=0,pretop=top; for(j=0;j<v[u].size();++j)sum+=size[v[u][j]]; if(sum==tot+top){ for(;v[u].size()==1&⊤u=v[u][0]) ins[w[v[u][0]]=stk[top--]]=v[u][0],++ac,--sum; if(sum)tot=top=0; } else{ if(sum)tot=tot+top-sum,top=0; } } for(i=1;i<=n;++i)printf("%d\n",w[i]); return 0;}
Jun 03, 2015 02:05:07 PM
请问程序中间那个没显示粗来的是什么。。。
Jun 03, 2015 02:24:25 PM
@DDD: 什么东西没显示出来啊
Jun 03, 2015 06:46:08 PM
@wyfcyx: 就是第47行FOR循环中间的那个
Jun 04, 2015 08:07:08 PM
@DDD: 玛雅这是什么...让我看看代码
Jun 04, 2015 08:09:05 PM
@wyfcyx: 现在换成了原汁原味的代码...这个bug是什么我也不太清楚...