P2168 [NOI2015]荷马史诗 k叉哈夫曼树

思路：哈夫曼编码

提交：1次（参考题解）

题解：类似合并果子$QwQ$

取出前$k$小（注意如果叶子结点不满的话要补全），合并起来再扔回堆里去。

#include<cstdio>

#include<iostream>

#include<queue>

#define ull unsigned long long

#define ll long long

#define R register ll

using namespace std;

#define pause (for(R i=1;i<=10000000000;++i))

#define In freopen("NOIPAK++.in","r",stdin)

#define Out freopen("out.out","w",stdout)

namespace Fread {

static char B[<<],*S=B,*D=B;

#ifndef JACK

#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)

#endif

inline ll g() {

    R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;

    if(ch==EOF) return EOF; do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;

} inline bool isempty(const char& ch) {return (ch<=||ch>=);}

inline void gs(char* s) {

    register char ch; while(isempty(ch=getchar()));

    do *s++=ch; while(!isempty(ch=getchar()));

}

} using Fread::g; using Fread::gs;

namespace Luitaryi {

struct node { ll w; int h; node() {}

    node(ll ww,int hh) {w=ww,h=hh;}

    inline bool operator <(const node& that) const {return w==that.w?h>that.h:w>that.w;}

};

priority_queue<node> q;

int n,k,lim; ll ans;

inline void main() {

    n=g(),k=g();

    for(R i=,x;i<=n;++i) x=g(),q.push(node(x,));

    if((n-)%(k-)) lim=k--(n-)%(k-);

    for(R i=;i<=lim;++i) q.push(node(,));

    lim+=n; while(q.size()>) { R W=,H=;

        for(R i=;i<=k;++i) {

            W+=q.top().w,H=max((ll)q.top().h,H);

            q.pop();

        } ans+=W; q.push(node(W,H+));

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

}

}

signed main() {

    Luitaryi::main(); return ;

}

---

2019.07.22