洛谷P2168 荷马史诗

堆     数学 

题意 实际上就是让你构造 一棵 K叉哈夫曼树

哈夫曼树其实就是路径权值和最小的树

路径权值权值和 = sigama 用的次数 * 深度

为了让路径权和最小

那么我们肯定是要让 用的次数越多的数深度越小

关于二叉哈夫曼树 我们是怎么构造的呢，

我们使用合并果子 一样构造的，每一次选择 最小的两个数 a b

然后将 a+b 加入序列中

然后K叉也差不多是这样

每次你可以选择 K 个数 然后 a1 a2 a3 a4 ...ak 然后将他们的和加入序列之中

但是有些时候你可能不到 k 个

因为 一次 合并越多肯定越优 ，因为你合并越多，等于说你重复用的数就越少了

因为最后一次合并时造成的 和最大 ，所以你要保证 最后一次 一定是 K个合并的

为了保证 一定是 K 个合并 你就可以 事先插入 若干个 0 确保 (n-1) % (k-1) == 0

然后这样就能确保 k 个k个合并一定能够完全合并了

然后就可以像合并果子 一样，每次选择前 k 小的，然后合并

然后我们用堆来维护 前 k 小的数

然后为了让深度最小，

为了让深度最小，我们在合并若干个 分数相同的 果子时 ，我们优先合并深度 较小的 ，尽量使深度不增加

然后我们堆就开两个关键字 第一关键字 按照 值从小到大排序 ，第二关键字 按照深度从小到大排序

 

1 #include 
     
        2 #define ll long long  3 using namespace std ;  4  5 const ll N = 100011 ;  6 struct node{ 7     ll val,deep ;  8 }; 9 struct cmp{10     bool operator() (node a,node b) 11     {12         if(a.val!=b.val) return a.val > b.val ; 13         return a.deep > b.deep ; 14     }15 };16 /*17 18 我们堆就开两个关键字  第一关键字 按照 值从小到大排序  ，第二关键字 按照深度从小到大排序  19 20 */ 21 priority_queue 
      
       
        ,cmp > Q ; 22 node p ; 23 ll n,k,w,sum,mx,ans ; 24 25 inline ll read() 26 { 27     ll x = 0 , f = 1 ; 28     char ch = getchar() ; 29     while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 30     while(ch>='0'&&ch<='9') { x = x * 10+ch-48 ; ch = getchar() ; } 31     return x * f ;   32 }33 34 int main() 35 {36     n = read() ;  w = n ;  k = read() ; 37     while((n-1) % (k-1)!=0 ) 38     {39         p.deep = 0 ; p.val = 0 ; 40         Q.push( p ) ; 41         n++ ; 42     }  43     n = w ; 44     for(ll i=1;i<=n;i++) 45     {46         p.deep = 0 ; p.val = read() ; 47         Q.push( p ) ; 48     }49     50     while(Q.size()>1) 51     {52         sum = 0 ; mx = 0 ; 53         for(ll i=1;i<=k;i++) 54         {55             sum+=Q.top().val ; 56             if( Q.top().deep > mx ) mx = Q.top().deep ; 57             Q.pop() ; 58         }59         p.val = sum ; p.deep = mx + 1 ; ans+=sum ; 60         Q.push( p ) ; 61     }62     printf("%lld\n%lld\n",ans,Q.top().deep) ; 63     return 0 ; 64 }