CF1303D Fill The Bag 题解

· · 题解

可能更好的阅读体验
题目传送门

题目大意

给定一个大小为 k 的背包以及 n 个物体。第 i 个物体的体积为 a_i，并且保证 a_i 为 2 的非负整数幂。现在你可以将一些物品切开，变成两个只有体积为原来一半的物体，求能把背包恰好装满至少需要切几次。

题目解析

不难想到二进制拆分。考虑贪心。
二进制拆分后，如果这一位没有大小恰好为 2^i 的物体，那么就去更大的切分。
如果从高到低考虑，我们不难发现这是假的，所以考虑从低到高位考虑。

具体的做法是这样的：
从低位到高位考虑，如果这一位恰好有大小为 2^i 的物体，那么就不需要切割，否则就找到最小的更大的物体来切割。

现在来证明这种做法的正确性和时间复杂度。
先证明正确性。不难发现如果将一个大小为 2^c 的物体分割成大小为 2^a 的物体，和把一个大小为 2^c 的物体分割成 2^b 的物体再分割成 2^a 的物体所需的次数是一样的（a<b<c）。所以这个做法是正确的。
然后证明时间复杂度。如果我们将分割了一个大小为 2^b 的物体到 2^a 的大小，那么就会多出 2^{a+1},2^{a+2},\dots,2^{b-2},2^{b-1} 这些物体。因此在暴力向上查找最小的更大的物体切割的时候，每个物体最多被搜到一次，所以可以保证时间复杂度为 \Theta\left(n\right)。

无解的情况是显然的，因为切割的时候总体积不变，所以只要 \sum a_i<k 的时候就无解，否则是有解的，因为你可以把所以的物体切成大小为 1 的大小。

核心代码：

int n,x,ans,t[39]; ll m,sum;
void work(){
    m=read(); n=read(); Me(t,0); sum=0; ans=0; int i,j;
    for(i=1;i<=n;i++) x=read(),sum+=x,t[(int)log2(x)]++;
    if(sum<m){ puts("-1"); return; } if(sum==m){ puts("0"); return; }
    for(i=0;i<31;i++){
        if(!t[i]&&(m&(1<<i))){ j=i; while(!t[j]) j++,ans++; t[j]--; for(j=j-1;j>=i;j--) t[j]++; }
        if(m&(1<<i)) t[i]--; t[i+1]+=(t[i]>>1);
    } print(ans),pc('\n'); return; 
}