文章目录

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5884
新学到的：

①判断是不是满的哈夫曼树：

为什么要判断是不是满的哈夫曼树喃？
因为满的哈夫曼树才是最优的
比如1 2 3 4，最多合并3个，并取最小的三个数1 2 3 就合并成6，然后再合并6 4

而是先合并1 2,成3，再合并3 3 4这样代价最小

k叉哈夫曼树：<mark>多余的节点=(N-1)%(k-1)</mark>
如果多余的节点计算出来是0，那就是满的
怎么理解喃？

看这个图，3叉哈夫曼树，每个只有最后一个是3个，而其他每层都只有（3-1）个，所以这个就很容易明白了

所以如果给的不是满的哈夫曼树，就阔以有两种方法变成满的：
①：把（多余的+1）个合并成1个
②：缺少的用0来补充

而我的代码是选择补充0，因为要方便补充0，因此才从大到小倒着来的

②不用优先队列

这道题因为有个二分就已经有个log了，所以用优先队列再来个log就有点卡时间了，因此这个优化在这道题中体现得淋漓尽致，我是先做的hdu1053练习的，我写得理解

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=2e5+5;
const int MOD=1e9+7;
LL a[maxn];
LL N,SUM;
queue<LL>que;
LL f(int k)
{
    LL res=0;
    while(!que.empty())que.pop();
    int now=N;
    if((N-1)%(k-1)!=0)
	{
		int tp=(N-1)%(k-1);//表示多余的 
		now+=(k-(tp+1));//加0的个数 
	}
    while(now+que.size()>=k)
    {
        LL tp=0;
        for(int i=1;i<=k;i++)
        {
            if(que.empty() || a[now]<=que.front())tp+=a[now--];//就是这里我now变成0了，但是我a[0]=0是个很小的数，所以就进去了，因此把a[0]=inf就行了 
            else if(now<1 || que.front()<=a[now])
            {
                tp+=que.front();
                que.pop();
            }
        }
        que.push(tp);
        res+=tp;
    }
    return res;
}
int main()
{ 
    int T;
    cin>>T;
    while(T--)
    {
        memset(a,0,sizeof a);
        a[0]=1e9;//原来是now变成0的时候,a[0]=0最小，所以把他赋值成无穷大 
        cin>>N>>SUM;
        for(int i=1;i<=N;i++)scanf("%lld",a+i);
        sort(a+1,a+1+N,greater<int>());//方便加0的个数，所以倒起来 
        LL L=2,R=N,mid;
        while(L<=R)
        {
            mid=L+R>>1;
            LL tp=f(mid);
            if(tp>SUM)L=mid+1;
            else R=mid-1;
        }
        LL ans=min(R+10,N);
        while(f(ans-1)<=SUM)ans--;//二分没学好，所以二分出来的答案再来枚举 
        printf("%lld\n",ans);
    }
}