HDU5884 二分+哈弗曼树

深藏阁楼爱情的钟 2022-05-15 09:56 122阅读 0赞

[传送门][Link 1]

huffman模板，如果每次取k个能取完，num=k，取不完先将n%（k-1）取完，再每次取k

#include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+10;
    typedef long long ll;
    int arr[N], n, limit;
    /****************************/
    int a[N], b[N<<3];
    bool Huffman(int k){
        int ai, bi, lenb, lena, num;
        bool first=true;
        ai=bi=lenb=lena=0;
    
        for(int i=1; i<=n; i++)
            a[lena++]=arr[i];
    
        ll s=0;
        while(n-ai+lenb-bi>1){
            if(first){
                if((n-k)%(k-1)==0)
                    num=k;
                else
                    num=n%(k-1);
                first=false;
            }
            else
                num=k;
            ll sum=0;
            while(num--){
                if(ai==lena)
                    sum+=b[bi++];
                else if(bi==lenb)
                    sum+=a[ai++];
                else if(a[ai]>b[bi])
                    sum+=b[bi++];
                else
                    sum+=a[ai++];
            }
            b[lenb++]=sum;
            s+=sum;
        }
        if(s>limit)
            return false;
        else
            return true;
    }
    /*****************************/
    int main(){
        int T;
        scanf("%d", &T);
        while(T--){
            scanf("%d%d", &n, &limit);
            for(int i=1; i<=n; i++)
                scanf("%d", arr+i);
    
            sort(arr+1, arr+1+n);
            int l=2, r=n, ans;
            while(l<=r){
                int mid=(l+r)>>1;
                if(Huffman(mid)){
                    ans=mid; r=mid-1;
                }
                else
                    l=mid+1;
            }
            printf("%d\n", ans);
        }
    
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=5884