P2168 NOI2015荷马史诗


这是k叉哈夫曼树的应用,在构造哈夫曼树的时候,可以用优先队列,这里可以采用pair简化代码,priotity_queue会依次判断大小,一个为当前节点值,另一个为高度,在k叉的时候,有可能会出现到根节点不足k叉的情况,一定不为最优解,所以可以先放虚节点
if((n-1)%(k-1)) pan=k-1-(n-1)%(k-1);
之后进行合并再重新插入,注意插入的时候高度要+1,最后的最小高度即为优先队列中最后根节点的高-1

#include<bits/stdc++.h>
using namespace std;
typedef pair<long long,long long> s;
priority_queue<s,vector<s>,greater<s> > q;
int n,k,pan=0;
long long ans=0;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        long long t;
        scanf("%lld",&t);
        q.push(s(t,1));
    }
    if((n-1)%(k-1)) pan=k-1-(n-1)%(k-1);
    for(int i=1;i<=pan;i++) q.push(s(0,1));
    pan+=n;
    while(pan>1)
    {
        s a;
        long long temp=0,maxx=0;
        for(int i=1;i<=k;i++)
        {
            a=q.top();
            temp+=a.first;
            maxx=max(maxx,a.second);
            q.pop();
        }
        ans+=temp;
        q.push(s(temp,maxx+1));
        pan-=k-1;
    }
    printf("%lld\n%lld\n",ans,q.top().second-1);
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
P1886滑动窗口 P1886滑动窗口
单调队列的经典问题,维护两个单调队列,一个递增一个递减 #include<bits/stdc++.h> using namespace std; const int maxn=1e6+10; int n,k,a[maxn]; int
2019-07-05
下一篇 
POJ3764The xor-longest Path POJ3764The xor-longest Path
这道题是高级版的让我们异或吧,思路依旧是对树dfs维护d[x]=d[fa[x]] xor w(x,fa[x])之后根据异或的性质x y共同路径被抵消,就不需要lca,直接d[x]+d[y]即可,而对于任意d中任意两个数要xor最大,就可以用
2019-07-05
  目录