codeforces-Ed82-D

codeforces-Ed82-D

七月 08, 2020

D.Fill The Bag

题意

你有一个 n 码的袋子，你还有 m 个盒子，第 i 个盒子的尺寸是 ai ，这里的每一个

ai 都是 2 的非负幂整数。

你可以把盒子分成大小相等的两部分。你的目标是完全装满袋子。

例如 n=10,a=[1,1,32] ，那么你必须把 32 码的盒子分成 16 码的两部分，然后把

16 码的盒子分开，你可以用 1 码，1 码，8 码的盒子装满袋子。

///被分割出来的16码 8码还有剩下的并不是直接扔掉

计算填充尺寸为 n 的袋子所需的最小分割数。

多组数据，无解输出 -1 。

先来讨论一下 -1 的情况：

考虑到分裂一个数不会影响到所有数的和。

那么我们将所有数都分裂成 1 ，由于和不变，此时 1 的个数为 ∑(i=1to m) a[i] ，

也就是说小于等于 ∑(i=1to m) a[i] 的数都可以被填出来。

故当 n>∑(i=1to m) a[i] 时，无解。

将 n 二进制拆分成 2^{k1}, 2^{k2},…, 2^{kc} 。

然后从低位（2^{k1} )到高位（2^{kc}）贪心填数。

假设我们当前处理到的数为 2^ki 。

首先考虑位数小于等于 ki 的所有数中，能不能凑成 2^ki ，若可以，直接填上去；否则考虑分裂位数大于 ki 的所有数中最小的那一个，使其经过若干次分裂，分裂成 2^ki 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll box[(int)1e5+4];
ll bit[60];
int main(){
    int t;cin>>t;
    while(t--){
        ll n,m,sum=0;cin>>n>>m;
        ll cnt,temp;
        for(int i=0;i<60;i++)bit[i]=0;
        for(int i=0;i<m;i++){
            cin>>box[i];
            sum+=box[i];
            temp=box[i];cnt=0;
            while(temp%2==0){
                temp/=2;
                cnt++;
            }
            bit[cnt]++;
        }
        if(sum<n){
            cout<<-1<<endl;
            continue;
        }
        ll ans=0;
        for(ll i=0;i<60;i++){
            if(n&(1ll<<i)){/// 若n的二进制第i位 为1 那么从第i位到最高位找是否有1可以直接用或分解
                for(ll j=i;j<60;j++){
                    if(bit[j]){///找到从第i位开始最低位的1 模拟减法 
			///比如需要一个1000 找到最低位的1在100000 那么100000 - 001000 =011000
                        bit[j]--;
                        for(ll k=i;k<j;k++)bit[k]++;
                        break;
                    }
                    ans++;///还未找到那么相当于 除2平分操作多一次
                }
            }
            bit[i+1]+=bit[i]/2;///在for循环到下一位时如果这一位的二进制1的个数大于2那么选择进位
			       ///等价于考虑位数小于等于 ki 的所有数中，能不能凑成 2^ki 
			       ///无法进位的数将不会被用到所以不用考虑
        }
        cout<<ans<<endl;
    }
}