P2168

Aryper · 2021-08-01 10:57:05 · 个人记录

[NOI2015] 荷马史诗

重载运算符不要写反。。。

然后这题是构造一个 k 叉的 Huffman 树。步骤如下：

将 n 个词汇的出现次数视为该点权值，加入小根堆。
加入权值为 0 的节点，直至节点个数 n 满足 (n-1)\mod (k-1)=0 。
每次从小根堆中取出 k 个，将它们的权值合并，设此点为 p ，则 p 的权值为 k 个点的权值之和。
将 p 加入小根堆。
重复上述 3 和 4 两步，直至堆的大小为 1 。

关于为什么要有第二步，可以以样例 2 为例，如果在去掉第二步的情况下做样例 2 ，就会发现有一个权值为 9 的节点是在倒数第二次合并中合并的，而最优的方法应该把这个节点在倒数第一次与另一个权值为 9 的节点以及先前的节点 p 合并。

出现这种问题的实质就是我们让一层内的合并不足 k 个，但偏偏让不足 k 个的情况发生在了最后一次合并。

所以加入了权值为 0 的节点，就让合并不足 k 个的情况出现在第一次合并，使答案更优。

这个贪心的最优大概就是自证不难了，毕竟让权值最大的节点离根节点的距离最小了，应该弄几个不等式就可以证了罢。。。

大概就是那个如果 a>b,c>d ，则(a-b)>0,(c-d)>0 ，则 (a-b)(c-d)>0 ，则 ac+bd>bc+ad 。实质上就是大乘大加小乘小会使答案更大，则大乘小、小乘大会使答案更小，即使答案更优。

同时注意这里的合并要使字符串长度最大者最小，那么我们还要将节点赋上深度的，在权值相同时，深度小（合并次数少）的优先。然而这个贪心也比较玄学，可以感性的作一个微扰的证明，假设我们让深度大的（假设为 d+1 ）先合并了（变为 d+2 ），会发现深度小的（假设为 d ）在之后依旧需要合并，最后得到的权值是不变的，这个比较显然。但是会知道深度的最大值一定 \ge d+2 ，显然没有先合并深度小的，使深度的最大值 \ge d+1 优，所以先合并深度小的会使答案更优。

为了维护这个深度和权值之间的优先级，我们可以使用一个结构体。然后就是重载运算符之类的事情了。。。

时间复杂度 O(n\log n) 。（大概）

代码：

#include<iostream>
#include<cstdio>
#include<queue>
#define ll long long
using namespace std;

struct node{
    ll w,h;
    bool operator <(const node&rhs) const {
        if(w==rhs.w) return h>rhs.h;
        return w>rhs.w;
    }
}t;

ll n,k,w,p,ans,h;

priority_queue<node> q;

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

int main() {

    n=read();k=read();

    for(ll i=1;i<=n;i++) {
        w=read();t.w=w;t.h=1;
        q.push(t);
    }

    while((q.size()-1)%(k-1)!=0) {
        t.w=0;t.h=1;q.push(t);
    }

    while(q.size()>=k) {
        p=0;h=-1;
        for(ll i=1;i<=k;i++) {
            p+=q.top().w;h=max(q.top().h,h);
            q.pop();
        }
        ans+=p;t.w=p;t.h=h+1;q.push(t);
    }

    write(ans);putchar('\n');
    write(q.top().h-1);

    return 0;
}