题解：AT_arc226_b [ARC226B] Bin-ary Packing

WangYangyu · 2026-08-10 11:19:07 · 题解

题目分析

:::info[题意简化] 有 n 个背包与 m 种物品，第 0 \le i < m 中物品的重量为 2^i，个数为 a_i。物品最终需要全部装入背包里，背包的重量为背包里物品重量之和，合理分配物品的位置使得最重的背包最轻，求出最重的背包重量。 :::

初看题意，一种贪心策略悄然浮出水面。由于物品重量为整数，且根据题意，第 i 种物品的重量恰为第 i-1 种物品重量的两倍，这是解题的关键。将物品种类 i 从 m-1 向 0 枚举，每一轮枚举具体流程如下。

• 初始时，定义一个优惠额度 w 为 0，代表该轮枚举可以优惠而不计入背包重量的物品数量，每一轮进行下面的分类讨论。
  • 若 a_i \ge w，则 a_i \leftarrow a_i-w，随后 w \leftarrow 0，接着执行下面的流程。
  • 若 a_i < w，则 w \leftarrow w-a_i，由于第 i 种物品的重量恰为第 i-1 种物品重量的两倍，所以枚举下一个 i 时优惠额度将翻倍，即 w \leftarrow 2w，接着进行下一轮的枚举。
• 我们可以想到一种尽量平均分配物品至背包中的贪心策略，则我们可以进行下面的分类讨论。
  • 若 n \mid a_i，则完全可以平均分配所有物品，那么此时最重的背包重量为 2^i \times \frac {a_i} n。
  • 若 n \nmid a_i，可设 a_i=kn+b，k 为 \lfloor \frac {a_i} n \rfloor，b 为 a_i \bmod n。先将其中的 k 个物品平均分配至 n 个背包中，再将剩下的 b 个物品平均分配到 b 个背包中。此时一定有 b 个背包的重量是 2^i \times (k+1)，剩下的 n-b 个的重量为 2^i \times k。若我们将所有的背包的装入的物品个数视为 k+1，则有 n-b 个背包不满足此数量，但是这份缺失的数量完全可以为下一种物品使用，且相同重量能承载的下一种物品是这一种物品的两倍，优惠额度 w \leftarrow 2(n-b)。
• 每一轮结束时，将当前轮次的最重的背包重量直接加入答案。

代码编写

#include <iostream>
typedef long long ll;
using namespace std;
const int M = 40;

// 单组测试数据的问题解决
inline void work() {
    // 变量定义与输入
    int n, m, a[M];
    cin >> n >> m;
    ll ans = 0, w = 0;
    for (int i = 0; i < m; i++)
        cin >> a[i];

    // 根据题解中的分析所进行的枚举，并执行题解中单次枚举的程序流程
    for (int i = m - 1; i >= 0; i--) {
        // 探寻物品数量与优惠额度的大小关系，并执行题解中的流程
        if (a[i] >= w)
            a[i] = a[i] - w, w = 0;
        else {
            w = 2 * (w - a[i]);
            continue;
        }

        // 探寻 a[i] 与 n 的整除性关系，并执行题解中的流程
        if (a[i] % n == 0)
            ans += (1ll << i) * (a[i] / n);
        else {
            int k = a[i] / n, b = a[i] % n;
            ans += (1ll << i) * (k + 1);
            w = 2 * (n - b);
        }
    }

    // 答案输出
    cout << ans << '\n';
}
int main(void) {
    int T;
    cin >> T;
    while (T--)
        work();
    return 0;
}

提交记录