洛谷P4437 排列 [HNOI/AHOI2018] 贪心
正解:贪心
解题报告:
发现做题龟速,,,所以懒得写题目大意辣自己$get$一下$QAQ$
首先看到$ai\leq n$,又当$a_{i}=j$时$j$在$i$的前面,所以就变成对于每个点$i$有一个约束,即要求第$a_i$个节点排在$i$的前面
考虑连边,对于$a_i$排在$i$的前面就从$a_i$向i连一条边就好
然后就变成,对于一个点i,一定有一条引向自己的边(但是当$a_{i}=0$的时候就相当于是麻油的),然后每次只能从$x$的前驱走向$x$
仔细一想这样构出来的要么是颗树要么是个环嘛(环就是麻油$a_{i}=0$嘛),如果是个环,那就是无解,最轻松,美滋滋打个-1就可以$return\ 0$了,就很爽
那如果是棵树,就变成辣这样子:有一棵树,一定要先选父亲节点再拓展到儿子节点,求那个式子$max$
(昂我想了下,,,如果有多个$a_{i}=0$其实是个森林,,,?不要在意这种细节反正麻油什么区别的$QwQ$
然后考虑,把所有节点从大到小排序,考虑加入序列
如果它麻油父亲,欧克,直接加进去,继续考虑下一个结点就好
如果它有父亲,那就要先选它父亲,由贪心可知选了它父亲之后选出来的第一个点一定就是点x,所以最终序列中一定是长这样儿的:...,$fa_{x}$,$x$,...
那么像我上面港有父亲的情况下,就相当于把这个节点和父亲节点合并成了一个元素,继续参与节点从大到小排序考虑加入的过程欸
那合并成一个元素之后怎么计算它的权值呢
考虑现在有两个元素,分别代表两个序列$A$,$B$,长度分别为$cnt_a$,$cnt_b$,权值和分别为$sum_a$,$sum_b$(这里的权值和指的是按照那个形式的,$1\cdot A_{1}+2\cdot A_{2}+3\cdot A_{3}$...这样子的$w$),序列和分别为$s_a$,$s_b$(这里的序列和指的是真的$A_1+A_2+A_3+A_4$这样儿的$w$
如果A优于B,就是说A放在B的后面的贡献要大一些,就可以列式:
$sum_b+sum_a+s_a\cdot cnt_b>sum_a+sum_b+s_b\cdot cnt_a$
整理得 $s_a/cnt_a>s_b/cnt_b$
所以可以得到对于一个元素,它的权值就是它的序列中所有点的权值的平均值
然后就做完辣!一直这么做下去就好!over!
再说下,实现的话可以考虑用堆,因为要改变权值所以用$pb$_$ds$中的待修改堆,$set$也成,然后还可以用堆+打标记(这个可以看$psj$的博客,,,他好像是用的优先队列+打标记?麻油仔细看$QAQ$
好神仙啊我天,,,
然后最后说下卡常
一个是不要无脑开$int$
一个是无脑加$rg$
然后最好是手写堆,快两三倍
没了
然后尝试用$set$然后发现太难打了所以代码咕了$QAQ$
然后好不容易打完辣$T$了两个点$QAQ$
然后我卡常卡了一天才过$QAQ$
我$jio$得我还是要学下手写堆和$pb$_$ds$,,,
#include<bits/stdc++.h> using namespace std; #define il inline #define rg register #define ll int #define llll long long #define gc getchar() #define rp(i,x,y) for(rg ll i=x;i<=y;++i) #define my(i,x,y) for(rg ll i=x;i>=y;--i) #define e(x) for(rg ll i=head[x];i;i=edge[i].nxt) #define t(i) edge[i].to const ll N=500000+10; ll n,ed_cnt,a[N],head[N],fa[N],sz[N],gg; llll as,w[N]; bool vis[N]; struct ed{ll to,nxt;}edge[N]; struct dat{ll pos,lth;llll sum;}; set<dat>Q; il ll read() { rg char ch=gc;rg ll x=0;rg bool y=1; while(ch!='-' && (ch<'0' || ch>'9'))ch=gc; if(ch=='-')ch=gc,y=0; while('0'<=ch && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc; return y?x:-x; } il bool operator < (rg dat x,rg dat y){rg llll tmp1=(llll)x.sum*y.lth,tmp2=(llll)y.sum*x.lth;return tmp1==tmp2?x.pos<y.pos:tmp1<tmp2;} il void ad(rg ll x,rg ll y){edge[++ed_cnt]=(ed){y,head[x]};head[x]=ed_cnt;} void dfs(rg ll x){vis[x]=1;++gg;e(x){if(vis[t(i)])printf("-1\n"),exit(0);dfs(t(i));}} il ll fd(rg ll x){return fa[x]==x?x:fa[x]=fd(fa[x]);} il dat cal(rg ll x){return (dat){x,sz[x],w[x]};} int main() { // freopen("pl.in","r",stdin);freopen("pl.out","w",stdout); n=read();rp(i,1,n)ad(a[i]=read(),i);dfs(0);if(gg!=n+1)return printf("-1"),0; rp(i,1,n)Q.insert((dat){i,sz[i]=1,w[i]=read()}),fa[i]=i;Q.insert((dat){0,sz[0]=1,w[0]=1e18}); while(!Q.empty()) { // printf("QAQ\n"); dat tmp=*Q.begin();Q.erase(tmp);if(!tmp.pos)return printf("%lld\n",as),0;ll fat=fd(a[tmp.pos]);dat fadat=cal(fat);Q.erase(fadat); as+=tmp.sum*fadat.lth;w[fat]+=tmp.sum;sz[fat]+=tmp.lth;fa[fd(tmp.pos)]=fat; Q.insert(cal(fat)); } printf("%lld\n",as); return 0; }