题目描述

难度分:$1900$

输入$n(1 \leq n \leq 10^6)$，$m(1 \leq m \leq 10^6)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$，长为$m$的数组 $b(0 \leq b[i] \leq 29)$。

• 有$n$个背包，第$i$个背包的容量为$a[i]$。
• 有$m$个物品，第$i$个物品的体积为$2^{b[i]}$。

把物品装入背包，对于每个背包，其中的物品体积之和不能超过背包容量。

所有背包的物品个数之和最大是多少？

输入样例$1$

5 3
8 4 3 2 2
3 2 2

输出样例$1$

2

输入样例$2$

10 6
1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0

输出样例$2$

6

算法

贪心

首先将每个$a[i]$按照二进制来拆，比如$3$可以拆成$1$和$2$，体积为$3$的背包可以装一个体积为$1$的物品和一个体积为$2$的物品，用一个$mp$数组来存储背包体积的信息，$mp[i]$表示体积为$2^i$的背包数量。优先对体积小的物品装箱，这样可以装更多的物品。因此先对$b$排序，按照从小到大的方式来安排每个$b[i]$应该怎么装箱。

如果有一个背包的体积恰好为$b[i]$，就直接装进去，这样一来体积为$2^{b[i]}$的背包就少一个，记录一下这个信息。否则就找到一个比$2^{b[i]}$大的背包（设体积为$2^V$），找不到就放弃对$b[i]$装箱。找到了就将它放入这个体积为$2^V$的背包，这时候剩下的体积$2^V-2^{b[i]}$又可以用二进制来拆，拆完之后更新这些体积的背包数量。

遍历所有的物品，对每个物品进行装箱就可以得到最多能够装多少个物品。

复杂度分析

时间复杂度

对$b$排序的时间复杂度为$O(mlog_2m)$，将$a$中每个元素进行二进制拆解的时间复杂度为$O(nlog_2mx)$，其中$mx$是最大的$a[i]$，本题中上限为$10^9$，所以$log_2mx$大概就是$30$。接下来对排序后的$b$进行遍历，当没有体积恰好为$2^{b[i]}$的背包时，需要在$O(log_2mx)$的时间复杂度下找一个体积更大的背包，并对这个背包的剩余体积进行二进制拆分，时间复杂度为$O(mlog_2mx)$。

综上，算法整体的时间复杂度为$O(mlog_2m+30(n+m))$。

空间复杂度

除了题目输入的$a$和$b$两个数组，还需要一个长度为$30$的频数数组$mp$，$mp[i]$表示体积为$2^i$的背包数量；而对$b$排序以快排为标准，空间复杂度为$O(log_2m)$。因此，算法整体的额外空间复杂度为$O(max(30,log2_m))$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#pragma GCC optimize(2)

using namespace std;
const int N = 1000010, M = 30;
int n, m, a[N], b[N], mp[M];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    memset(mp, 0, sizeof mp);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        for(int j = 0; j < M; j++) {
            if((a[i]>>j) == 0) break;
            if(a[i]>>j&1) mp[j]++;
        }
    }
    for(int i = 1; i <= m; i++) {
        cin >> b[i];
    }
    int ans = 0;
    sort(b + 1, b + m + 1);
    for(int i = 1; i <= m; i++) {
        if(mp[b[i]] > 0) {
            mp[b[i]]--;
            ans++;
        }else {
            int V = 0;
            for(int v = b[i] + 1; v < M; v++) {
                if(mp[v] > 0) {
                    V = v;
                    break;
                }
            }
            if(V) {
                mp[V]--;
                ans++;
                int remain = (1<<V) - (1<<b[i]);
                for(int j = 0; j < M; j++) {
                    if((remain<<j) == 0) break;
                    if(remain>>j&1) mp[j]++;
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}