题目传送门(BZOJ)

题解 :

把所有砝码排个序, 从小到大放一定是最优秀的, 问题在于往哪个包里放.
由于题中性质 : 对于任意两个砝码, 一个重量一定是另一个的整数倍,
故本质不同的砝码数量应该在$\log 10^9$以下
我们把它变成一个混合进制的背包, 从高到低对应一个数, 这样只需要开大小$\log 10^9$的即可
把所有题中给的背包容量都从高到低放到给这个进制背包
以样例为例 :
进制背包 : $(12, 4, 2) (BASE)$
$w_1$ : $(1, 0, 0)+1$ (这个1是不可能用得到的, 直接忽略即可)
$w_2$ : $(0, 2, 0)+1$ (同样忽略)
这样我们实际的进制背包容量就是 (1, 2, 0);
现在开始往里放东西, 首先排好序
对于一件大小为 $2$ 的物品, 我们先从它对应的进制位上看还有没有容量
如果有, 直接扣掉容量累加答案即可
否则, 我们从前面最近的有值位借1, 直接模拟一下减法即可
如果在塞一个物品的时候已经没位置了, 直接 break; 就行
具体细节参见代码

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 100100;int a[35], b[35], v[N], w[N]; int main() { int n, m, ans = 0; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++ ) scanf("%d", &v[i]); for(int i = 1; i <= m; i ++ ) scanf("%d", &w[i]); sort(w+1, w+m+1); for(int i = 1; i <= m; i ++ ) { if(w[i] > b[*b]) b[++*b] = w[i]; w[i] = *b; } for(int i = 1; i <= n; i ++ ) for(int j = *b; j; j -- ) a[j] += v[i]/b[j], v[i] %= b[j]; for(int i = 1; i <= m; i ++ ) { if(a[w[i]]) a[w[i]] --, ans ++; else { bool flg = true; for(int j = w[i]; j <= *b; j ++ ) { if(a[j]) { a[j] --, flg = false; break; } a[j] = b[j+1]/b[j]-1; } if(flg) break; ans ++; } } printf("%d\n", ans);}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<