BZOJ 1110: [POI2007]砝码 – [贪心]

题目传送门(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 
#include 
#include 
#include 
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原创, 转载必须以链接形式注明>原文链接<