ACGO CSP/J 比赛T2题解
2026-10-20 20:38:27
发布于:广东
前言
上手难度挺高(我太菜了,我是垃圾,这么简单的结论我想了那么久?)
本题价值
题解
大胆猜结论:无脑往单个墙里填大的。
如果没有 都是 的幂次这个约束的话,上述贪心就不适用了。
比如墙宽度为 ,板子长度分别为 ,你无脑填大的答案是 ,但实际是 。
我们想证明无脑填大的是不劣的,也就是证明填 个大的一定不劣于填 个小的。
这个显然,因为 的幂次的性质,,而当前面项的指数变小时式子取到小于号,所以是不劣的。
然后做完了。拿个桶存 随便搞即可。
妈的,咋这么简单,我做的时候真不会证,如此状态,如何 S1???
for(int i = 1;i<=n;++i){
int x;
cin>>x;
t[(int)(log2(x))]++;
}
int tot = 0,rem = n;
while(rem){
int p = w;
++tot;
for(int i = 20;i>=0;--i){
if(t[i]){
int can = p/(1<<i);
can = min(can,t[i]);
p-=can*(1<<i);
rem-=can;
t[i]-=can;
}
}
}
cout<<tot<<'\n';
全部评论 2
d
2026-10-21 来自 广东
0d
2026-10-20 来自 广东
0

















有帮助,赞一个