【ARC#226】B题题解
flywen
·
·
题解
从大到小枚举物品体积，设现在物品体积为 $2^i$，设它与比它大的所有物品的体积（前缀体积）等价于 $s$ 个体积为 $2^i$ 物品。考虑直接放进 $n$ 个袋子，则最终答案一定不小于理想的 $\lceil \frac{s}{n}\rceil\times 2^i$。
感想 @[rabbit_mygo](https://www.luogu.com.cn/user/1678847) 的正确性证明。
归纳法证明，$i=m−1$ 时正确性显然。
考虑一个贪心：从大到小考虑物品。每次优先放入使用体积最小的袋子。则体积为 $2^i$ 的物品能产生贡献，当且仅当现在所有袋子的使用体积均为 $v$。而 $v$ 一定是 $2^i$ 的倍数，故将更大的物品拆成体积为 $2^i$ 不会使得答案变小。
既然理想情况没有变小，那么就是真实下界。
```cpp
ans=sum=0;
for(int i=m-1;i>=0;--i){
sum*=2;
sum+=a[i];
ans=max(ans,(sum+n-1)/n*(1ll<<i));
}
printf("%lld\n",ans);
//……如此强大……
//只要你想，就可以做到。
//但知道这悲惨的理念之后，你还能挥起你的骨钉吗？要是你知道了自己的身世呢？……
//那就放手去做吧，圣巢的鬼魂！前进。去把那标记印在你的外壳上，然后称王。
```