荷马史诗

哈夫曼树： 最小化权值与距离的乘积和

对于形如 \(min\{\sum w_i \times l_i\}\) 的形式,都可以考虑采用哈夫曼树来贪心

荷马史诗

哈夫曼树和trie树结合考察 两者有相似的性质, 并且满足哈夫曼树要求的条件

int main()
{
	n=read(); k=read();	
	for(int i=1;i<=n;i++) w[i]=read(),q.push( (Node){w[i],0}   );
	if((n-1)%(k-1)) for(int i=1;i<=( (k-1)-(n-1)%(k-1) );i++) q.push(  (Node){0,0} );
	ll ans1=0,ans2=0;
	while(q.size()>1)
	{
		ll tmp=0,tt=0;
		for(int i=1;i<=k;i++) tmp+=q.top().val,tt=max(tt,q.top().cnt),q.pop();
		ans1+=tmp;
		q.push( (Node){tmp,tt+1} );		
	}
	ans2=q.top().cnt;
	printf("%lld\n%lld\n",ans1,ans2);
	return 0;
}

注意:

1. read改成longlong后 所有的读入变量都要开longlong
2. 多x成为y的倍数和少x成为y的倍数是两个不同的问题