题目链接：「萌新首秀」千校新生编程排位赛·第二场

一句话概括解法：每张打印卡只有「买 / 不买」两种选择，M ≤ 18 → 枚举 2^M 种组合，取花费最小。这道题是二进制枚举（位掩码枚举）的模板题。

一、题目复述

小蓝要打印 Q 页资料，打印店有两种方式：

  • 直接打印：每页 P 元；
  • 打印卡：共有 M 种卡，第 i 种需要花 Cᵢ 元购买，买后最多可打印 Lᵢ 页。每种卡最多购买一次，可以同时买多种。没用的页数不退钱。

求打印完全部 Q 页资料，最少要花多少钱。

数据范围：

变量 范围 提示
Q, P 1 ~ 10⁹ Q × P 最大 10¹⁸，必须用 long long
M 1 ~ 18 2¹⁸ = 262144，这是本题的突破口
Lᵢ, Cᵢ 1 ~ 10⁹ 累加会超过 int

二、把问题抽象成「子集选择」

先写出花费公式。假设我们决定买下一个卡片集合 S：

1
2
3
4
5
总页数 = Σ Lᵢ  (i ∈ S)
总卡费 = Σ Cᵢ  (i ∈ S)

如果 总页数 ≥ Q：花费 = 总卡费
如果 总页数 < Q：花费 = 总卡费 + (Q - 总页数) × P    // 缺的页数按原价补齐

要回答的问题就是：在所有可能的集合 S 里，哪个花费最小？

注意公式里有个细节：卡片页数买多了不退钱，所以「总页数 ≥ Q」时不能再去减什么，直接就是卡费总和。

三、为什么这题不能贪心

很容易想到的贪心是：按「每页单价 Cᵢ / Lᵢ」从便宜到贵买卡片。这个思路是错的。

3.1 反例

设 Q = 10，P = 100（直接打印非常贵），两张卡：

卡片 页数 价格 单价
卡 A 6 1 ≈ 0.167 元/页
卡 B 10 2 0.2 元/页
  • 按单价贪心：卡 A 更便宜，先买 A。花 1 元得 6 页，还差 4 页。这时再权衡 B——加 2 元能省掉 4 × 100 = 400 元的直接打印费，划算，于是也买 B。总花费 1 + 2 = 3 元。
  • 真正的最优：只买卡 B，10 ≥ 10 直接覆盖，花费 2 元。

贪心多花了 50%。

3.2 根因

卡片之间会互相覆盖：买下 A 之后，B 的 10 页里有 6 页被 A「重复占掉了」，B 的实际收益从 10 页缩水成 4 页，性价比完全变了。

也就是说，每张卡的边际收益依赖于已经选了哪些卡，这破坏了贪心所依赖的「选择之间互相独立」的前提。

卡片不可拆分是这道题必须枚举的根本原因。如果允许买「半张卡」（按页买），那贪心就是对的——而按页买恰好就是「直接打印」这一项。

四、核心知识点：二进制枚举（位掩码枚举）

4.1 抓住 M ≤ 18 这个提示

数据范围把 M 卡在 18，不是随便定的：

1
2¹⁸ = 262144

如果把每种卡都看作一次「买 / 不买」的 0/1 决策，那么所有可能的购买方案一共只有 2^M 种。即使每种方案都花 O(M) 去统计，总共也只有

1
262144 × 18 ≈ 4.7 × 10⁶

次运算，1 秒内轻松跑完。出题人给 M ≤ 18，就是在明示「枚举所有子集」。

4.2 用二进制数给「子集」编号

一个 M 位的二进制数，恰好可以表示一个子集：第 j 位是 1，就表示第 j 张卡被买了。

以 M = 3 为例：

掩码 (十进制) 二进制 含义
0 000 一张都不买
1 001 只买第 0 张
2 010 只买第 1 张
5 101 买第 0 张和第 2 张
7 111 三张全买

mask 从 0 枚举到 2^M - 1，就把所有子集一个不落、不重不漏地遍历了一遍。这就是「二进制枚举」这个名字的由来。

4.3 三个必须记住的位运算

写法 含义
1 << j 只有第 j 位是 1，其余全是 0（相当于 2 的 j 次方）
mask & (1 << j) 取 mask 的第 j 位。结果为 0 表示没选，非 0 表示选中
(mask >> j) & 1 同上，结果是干净的 0 或 1

再配合循环范围 1 << M（即 2^M，所有子集的个数），模板就齐了。

4.4 整体流程

五、代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
    ll Q, P;
    int M;
    cin >> Q >> P >> M;              // Q、P 最大 1e9，必须 long long

    vector<ll> L(M), C(M);           // 页数、价格同样用 long long，避免累加溢出
    for (int i = 0; i < M; i++) cin >> L[i] >> C[i];

    ll ans = Q * P;                  // 方案 0：一张卡都不买（Q*P 最大 1e18，需要 long long）

    for (int mask = 0; mask < (1 << M); mask++) {   // 枚举全部 2^M 种买卡组合
        ll sumL = 0, sumC = 0;

        for (int j = 0; j < M; j++) {               // 逐一检查第 j 张卡是否被选中
            if (mask & (1 << j)) {                  // 第 j 位为 1 → 买了这张卡
                sumL += L[j];                       // 累计可打印页数
                sumC += C[j];                       // 累计卡费
            }
        }

        // 卡片没覆盖到的页数，只能按 P 元/页 直接打印
        if (sumL < Q) sumC += (Q - sumL) * P;

        if (sumC < ans) ans = sumC;                 // 打擂台，取最小
    }

    cout << ans;
    return 0;
}

几点说明：

  • ans 直接初始化为 Q * P，这样「一张卡都不买」这种情况就自动包含进来了，不用额外特判；
  • 卡片页数超过 Q 时不需要也不应该做减法——多买的页数不退钱；
  • 内层循环顺序无所谓，选中的卡累加即可。

六、样例验证

输入：

1
2
3
20 5 2
8 20
10 30

Q = 20，P = 5，两张卡：卡 0（8 页 20 元）、卡 1（10 页 30 元）。四种组合全部枚举：

mask 买哪些卡 sumL sumC 直接打印补齐 总花费
00 都不买 0 0 20 × 5 = 100 100
01 卡 0 8 20 12 × 5 = 60 80
10 卡 1 10 30 10 × 5 = 50 80
11 卡 0 + 卡 1 18 50 2 × 5 = 10 60

最小值 60，与样例输出一致。

顺带看一个反直觉的点：卡 0 的单价是 20 ÷ 8 = 2.5 元/页，比卡 1 的 30 ÷ 10 = 3 元/页更划算，但最优解偏偏是两张都买。原因是「边际收益」在起作用：

  • 从方案 01（80 元）再加买卡 1：多花 30 元，顶掉 12 页原价打印中的 10 页（省 50 元），净省 20 元 → 60 元；
  • 从方案 10（80 元）再加买卡 0：多花 20 元，顶掉 10 页原价打印中的 8 页（省 40 元），同样净省 20 元 → 60 元。

两张卡各自的边际收益都是正的，所以都要买。单看单价排序是判断不出这个结论的——这正是必须枚举全部子集的原因。

七、易错点清单

  1. 溢出：Q × P 最大 10¹⁸，int 上限只有约 2.1 × 10⁹，用 int 必炸。凡是看到 10⁹ 级别的量，先想 long long。

  2. 位运算与比较运算符的优先级：== 的优先级高于 &，所以下面这种写法是错的：

    1
    if (mask & (1 << j) == 1)     // 错误！会被解析成 mask & ((1 << j) == 1)

    正确写法是给位运算加括号：

    1
    2
    if ((mask & (1 << j)) != 0)   // 正确
    if (mask & (1 << j))          // 正确，非 0 即为真

  3. 枚举上界写错：是 mask < (1 << M)，不是 <=。写成 <= 会多枚举一种不存在的组合（越界一位）。

  4. 1 << M 的隐患：本题 M ≤ 18 安全，但如果以后遇到 M 可能到 31 或更大，必须写成 1LL << M——1 是 int，左移 31 位会溢出。
  5. 忘了「一张都不买」：初值一定要设成 Q * P，不能设成无穷大后只在循环里更新。
  6. 下标对应关系：mask 的第 j 位对应第 j 张卡（从 0 开始数）。如果程序里对卡片做了排序，记得位号跟着一起变，不要错位。

八、拓展一：枚举子集的另两种写法

8.1 递归（DFS）枚举

思路完全一样，只是把「枚举掩码」换成「对每张卡做决策」：

1
2
3
4
5
6
7
8
9
void dfs(int j, ll sumL, ll sumC) {   // 决定第 j 张卡买不买
    if (j == M) {
        ll cost = sumC + (sumL < Q ? (Q - sumL) * P : 0);
        ans = min(ans, cost);
        return;
    }
    dfs(j + 1, sumL, sumC);                 // 不买第 j 张
    dfs(j + 1, sumL + L[j], sumC + C[j]);   // 买第 j 张
}

好处是「一边搜一边累计」，不需要每轮重新扫描全部卡片；坏处是要处理全局变量和递归边界。

8.2 枚举某个集合的所有子集

有时候题目要求「在给定集合 mask 内部再枚举它的子集」，用这个技巧，复杂度是 3^M：

1
2
3
for (int sub = mask; sub; sub = (sub - 1) & mask) {
    // sub 依次取遍 mask 的所有非空子集
}

它的原理是「子集枚举的减一法」：sub - 1 把最低位的 1 变成 0 并把更低位全置 1，再 & mask 就跳回 mask 的范围内。这个技巧在状压 DP 里非常常用，先记个脸熟。

8.3 如果 M 更大呢

M ≤ 18 才能暴力枚举。如果出题人把 M 放大到 40，2⁴⁰ 就不可能了，这时候要换武器：

  • 折半枚举（meet in the middle）：把卡片分成两半，各枚举 2²⁰ 种，排序后双指针/二分合并；
  • 0/1 背包：f[j] 表示「至少覆盖 j 页的最小花费」，但这里 Q 高达 10⁹，数组开不下，所以本题不适用。

看到数据范围就能猜到算法，是竞赛里非常重要的直觉：M ≤ 18 → 指数枚举；N ≤ 2000 → O(N²)；N ≤ 10⁵ → O(N log N)。

九、小结与模板记忆

  • 模型：每张卡「买 / 不买」→ 求最优子集，这是一个子集选择问题。
  • 贪心为什么不行：卡片的收益会互相覆盖，边际收益随已选集合变化，不满足贪心选择性质。
  • 突破口：M ≤ 18 → 2¹⁸ ≈ 2.6 × 10⁵ 种组合，全枚举 + O(M) 统计 = 约 5 × 10⁶ 次运算。
  • 二进制枚举模板：
1
2
3
4
5
for (int mask = 0; mask < (1 << M); mask++) {
    for (int j = 0; j < M; j++) {
        if (mask & (1 << j)) { /* 第 j 个元素被选中 */ }
    }
}
  • 数据范围提醒：10⁹ 级别的数一律 long long；mask & (1 << j) 记得加括号。

这道题思路不超过十行，但完整踩一遍坑（溢出、优先级、上界、初值、贪心陷阱）之后，二进制枚举这个工具就算真正拿到手里了——后面学状压 DP、集合覆盖、TSP，用的都是同一套东西。