LOJ#2132. 「NOI2015」荷马史诗

$n \leq 100000$个数字，放进$k$叉树里，一个点只能放一个数，使所有数字乘以各自深度这个值之和最小的同时，最大深度的数字最小。

哈夫曼。这是我刚学OI那段时间看到的，感觉就是个很无聊的贪心，而且密码学我也不学深对哈夫曼的应用也了解不多，没想到出现在noi。

原来的哈夫曼只需要每次拿k个最小的数出来，建一个他们共同的父亲并在一起，当作一个权值为他们权值之和的新点，用堆可以实现；由于$(n-1) \mod (k-1)$不一定为0，需要补几个0点进去。相对于原来的哈夫曼，这里多了个深度限制，那只需要把堆里元素再记一下最大深度就可以了。

 //#include<iostream>

 #include<cstring>

 #include<cstdio>

 //#include<math.h>

 //#include<set>

 #include<queue>

 //#include<bitset>

 //#include<vector>

 #include<algorithm>

 #include<stdlib.h>

 using namespace std;

 #define LL long long

 int qread()

 {

     char c; int s=,f=; while ((c=getchar())<'' || c>'') (c=='-') && (f=-);

     do s=s*+c-''; while ((c=getchar())>='' && c<=''); return s*f;

 }

 //Pay attention to '-' , LL and double of qread!!!!

 int n,K;

 #define maxn 200011

 struct qnode

 {

     LL v; int dep;

     bool operator > (const qnode &b) const {return v>b.v || (v==b.v && dep>b.dep);}

 };

 priority_queue<qnode,vector<qnode>,greater<qnode> > q;

 int main()

 {

     n=qread(); K=qread(); LL v;

     for (int i=;i<=n;i++) {scanf("%lld",&v); q.push((qnode){v,});}

     if ((n-)%(K-)) for (int i=,to=(K-)-(n-)%(K-);i<=to;i++) q.push((qnode){,}),n++;

     LL ans=;

     for (int i=,to=(n-)/(K-);i<=to;i++)

     {

         LL nv=; int nd=;

         for (int j=;j<=K;j++) nv+=q.top().v,nd=max(nd,q.top().dep),q.pop();

         ans+=nv; q.push((qnode){nv,nd+});

     }

     printf("%lld\n%d\n",ans,q.top().dep);

     return ;

 }

巴特西

LOJ#2132. 「NOI2015」荷马史诗

最新文章

热门文章