Educational Codeforces Round 82 (Rated for Div. 2)：D. Fill The Bag

不念不忘少年蓝@ 2023-07-05 10:12 48阅读 0赞

**Discription**  
You have a bag of size n. Also you have m boxes. The size of i-th box is ai, where each ai is an integer non-negative power of two.

You can divide boxes into two parts of equal size. Your goal is to fill the bag completely.

For example, if n=10 and a=\[1,1,32\] then you have to divide the box of size 32 into two parts of size 16, and then divide the box of size 16. So you can fill the bag with boxes of size 1, 1 and 8.

Calculate the minimum number of divisions required to fill the bag of size n.

**Input**  
The first line contains one integer t (1≤t≤1000) — the number of test cases.

The first line of each test case contains two integers n and m (1≤n≤1018,1≤m≤105) — the size of bag and the number of boxes, respectively.

The second line of each test case contains m integers a1,a2,…,am (1≤ai≤109) — the sizes of boxes. It is guaranteed that each ai is a power of two.

It is also guaranteed that sum of all m over all test cases does not exceed 105.

**Output**  
For each test case print one integer — the minimum number of divisions required to fill the bag of size n (or −1, if it is impossible).

**Example**  
**input**

3
    10 3
    1 32 1
    23 4
    16 1 4 1
    20 5
    2 1 16 1 8

**output**

2
    -1
    0

**题意**  
给定一个n，和m个数，每个数都保证是2的幂次，可以将某个数拆成两个相同的数，进而拆下去。问拆的最小的次数，能正好凑出来n。

**思路**  
将n拆成多个2的幂次和的形式，如，18=2^4 + 2^1;  
将所有的不同大小的口袋通过下标存起来。  
从低位开始忘高位找，两个相同的地位可以合成一个比当前位高一位的数，如果当前位不够则从高位拆。

**AC代码**

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=4e5+5;
    int T;
    ll n,m,k,ans,flag;
    ll a[maxn],c[maxn],p[maxn],sum[maxn];
    char s[maxn];
    bool ok[maxn];
    int main()
    { 
        p[0]=1;
        for(int i=1; i<=31; i++)
            p[i]=(p[i-1]<<1);
        scanf("%d",&T);
        while(T--)
        { 
            for(int i=0; i<=31; i++)
                c[i]=0;
            scanf("%lld%lld",&n,&m);
            ll sum1=0;
            for(int i=1; i<=m; i++)
            { 
                scanf("%lld",&a[i]);
                sum1+=a[i];
                ll x=a[i];
                ll tmp=0;
                while(x)
                { 
                    tmp++;
                    x>>=1;
                }
                c[tmp-1]++;
            }
            if(sum1<n)
            { 
                cout<<-1<<endl;
                continue;
            }
            ans=0;
            for(int i=0;i<=30;i++)
            { 
                sum[i]=(n&1);
                n>>=1;
            }//将n拆成几个2的幂次方相加的形式
            for(int i=0;i<=30;i++)
            { 
                if(sum[i])
                { 
                    if(sum[i]<=c[i])
                    { 
                        c[i]-=sum[i];
                        sum[i]=0;
                        c[i+1]+=c[i]/2;//可以将低次幂的合成高次幂来使用
                    }
                    else
                    { 
                        sum[i]-=c[i];
                        c[i]=0;
                        int j=i+1;
                        ll k=(sum[i]+1)/2;//若不够则从上一阶拆
                        if(c[j]>=k)
                        { 
                            ans+=k;
                            c[j]-=k;
                            k=0;
                        }//若高位够，直接拆
                        else
                        { 
                            k-=c[j];
                            ans+=k;
                            c[j]=0;
                            sum[j]+=k;
                        }//高位不够则要往更高位拆
                    }
                }
                else
                    c[i+1]+=c[i]/2;
            }
            printf("%lld\n",ans);
        }
        return 0;
    }