luogu P2168 [NOI2015]荷马史诗

因为要满足任何一个串都不是另一个的前缀，满足Huffman树的性质，所以直接像合并果子那样进行操作即可。

好吧，还要满足(n-1)mod(k-1)==0，若不满足，再补几个0就好啦。

题目中还要满足最长的串尽量短，只需在面对相同权值时取出深度较小的即可。

在此我主要想说一下如何用priority_tree来实现重载优先级。

这和普通的不一样，一般要使得较小的优先的话，一般是这样写

bool operator < (const Node &i) const{
      if(w==i.w) return r<i.r;
      return w<i.w;        
}

但在优先队列里面，它貌似是反着的，要满足较小的优先，要写成这样（本蒟蒻只会这么写QAQ）

bool operator < (const Node &i)const{
    if(w==i.w) return r>i.r;
    return w>i.w;
}

具体原理我也不懂。。。。

最后附上代码

#include<iostream>
#include<cstdio>
#include<queue>
#define ll long long
using namespace std;
struct Node{
    ll w;int r;
    Node(ll w=0,int r=0):w(w),r(r){}
    bool operator < (const Node &i)const{
        if(w==i.w) return r>i.r;
        return w>i.w;
    }
}a[100010];
priority_queue<Node> q;
int n,k,f;
ll ans;
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i].w);a[i].r=0;q.push(a[i]);
    }
    if((n-1)%(k-1)){
        for(int i=1;i<=(k-1)-((n-1)%(k-1));i++) q.push(Node(0,0));
    } 
    while(q.size()>1){
        ll sum=0;int c=0;
        for(int i=1;i<=k;i++){
            Node x=q.top();q.pop();sum+=x.w;c=max(c,x.r);
        }
        ans+=sum;f=max(f,c+1);q.push(Node(sum,c+1));
    }
    printf("%lld
%d",ans,f);return 0;
}