书 - 题目列表

形式化题目

有 $n$ 个物品，第 $i$ 个物品"选"得收益 $a_i$ ，"不选"得收益 $b_i$ ；选的数量不超过 $m$ 。求最大总收益。

思路

一句话本质：先默认全部不带走（基准 $\sum b_i$ ），把第 $i$ 本书改为带走只会带来与其他书无关的变化 $d_i = a_i - b_i$ ，于是原问题变成"从 $n$ 个数里挑至多 $m$ 个正数使和最大"——只取正的，超过 $m$ 个就取前 $m$ 大。

问题？ 每本书带与不带各有一个收益，一共 $2^n$ 种方案，直接枚举不可能；能不能把两个收益压缩成一个数？

两种收益之间的差是固定的：所有书都"不带走"的收益 $\sum b_i$ 是一个公共起点。把第 $i$ 本书从"不带走"改成"带走"，总收益只会变化 $a_i - b_i$ ，与其他书怎么选无关。所以每本书只需要一个数 $d_i = a_i - b_i$ ：它自己的边际收益。

问题？ 边际收益 $d_i$ 能直接告诉我们这本书要不要带走吗？

能。 $d_i > 0$ 说明带走比不带走多赚，应该带走； $d_i \leqslant 0$ 说明带走只会让收益更差，不带走更好。总收益 = 基准 $\sum b_i$ + 所有被带走的书的 $d_i$ 之和。

这张表用样例 #1 展示基准转换：

$i$	$a_i$ （带走）	$b_i$ （不带走）	$d_i = a_i - b_i$	决策
1	5	3	2	带走
2	4	6	-2	不带走

看决策列：只有 $d_i > 0$ 的书被带走， $d_2 = -2 \leqslant 0$ 的书不带走。基准 $\sum b_i = 3 + 6 = 9$ ，答案 $9 + 2 = 11$ ，与样例一致。

问题？ 正 $d_i$ 的书超过 $m$ 本怎么办？凑不满 $m$ 本又怎么办？

超过 $m$ 本时名额不够，只能挑 $d_i$ 最大的前 $m$ 本：名额冲突时把 $d$ 更小的书换成 $d$ 更大的书，收益只会增加。凑不满 $m$ 本时全带走即可——限制是"最多 $m$ 本"，带 $d_i \leqslant 0$ 的书只会白白降低收益，名额不必用满。

问题？ 前 $m$ 大怎么取？数值上有什么坑？

$n \leqslant 5 \times 10^5$ ，用 nth_element 找到第 $m$ 大就能把前 $m$ 大放到前面，均摊 $O(n)$ 。收益最大约 $10^9 \times 5 \times 10^5 = 5 \times 10^{14}$ ，超出 int，必须用 long long。

先用一个枚举所有方案的暴力验证上面的分解没有丢掉任何方案：

cpp

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-28 23:40
 * update_at: 2026-08-28 23:40
 */
// brute.cpp：小数据暴力解，使用 01 序列 / 选择序列递归枚举所有可能。
// 每本书一个选择 choose[i]：0 不带走，1 带走。
// 只适合 n <= 15 的小数据（2^n 种方案），用于验证思路并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;

int n, m;
long long a[MAXN], b[MAXN]; // a[i] 带走收益，b[i] 不带走收益
int choose[MAXN];           // choose[i]：第 i 本书的选择，0 不带走，1 带走
long long ans;

// 检查当前完整 choose[1..n] 是否合法：带走的数量不超过 m
bool check() {
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (choose[i] == 1) cnt++;
    return cnt <= m;
}

// 统计当前完整 choose[1..n] 的总收益
long long calc_answer() {
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        if (choose[i] == 1) sum += a[i];
        else sum += b[i];
    }
    return sum;
}

// 这一层枚举第 dep 本书的 01 选择：0 不带走，1 带走
void dfs(int dep) {
    if (dep == n + 1) {
        // 一条完整选择序列生成后，统一检查合法性并更新答案
        if (check()) {
            long long value = calc_answer();
            if (ans < value) ans = value;
        }
        return;
    }
    for (int i = 0; i <= 1; i++) {
        choose[dep] = i;
        dfs(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    ans = LLONG_MIN;
    dfs(1);
    cout << ans << '\n';
    return 0;
}

这个暴力把问题看成一条 01 选择序列：choose[i] = 0/1 表示第 $i$ 本书不带走/带走，递归生成完整序列后检查带走数量 $\leqslant m$ 再统计收益。它枚举 $2^n$ 种方案，只适合 $n \leqslant 15$ 的小数据，但它体现的"每本书决策独立"正是基准转换能成立的依据。

代码

cpp

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-28 23:40
 * update_at: 2026-08-28 23:40
 */
// main.cpp：带走至多 m 本书，求最大总收益。
// 思路：基准转换——默认全部不带走（基准 = Σ b_i），
// 把第 i 本书改为带走只带来与其他书无关的变化 d_i = a_i - b_i，
// 所以只取 d_i > 0 的中最大的前 m 个累加。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;

int n, m;              // 书的数量、最多可带走数量
long long a[MAXN];     // a[i]：带走第 i 本书的收益
long long b[MAXN];     // b[i]：不带走第 i 本书的收益
long long diff[MAXN];  // diff[1..cnt]：正边际收益 d_i = a_i - b_i
int cnt;               // 正边际收益的个数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    long long base = 0; // 基准收益：所有书都不带走
    for (int i = 1; i <= n; i++) {
        base += b[i];
        long long d = a[i] - b[i];
        if (d > 0) diff[++cnt] = d; // 只有 d > 0 的书才值得带走
    }

    // 正边际收益超过 m 个时，只保留最大的前 m 个
    if (cnt > m) {
        nth_element(diff + 1, diff + m + 1, diff + cnt + 1,
                    greater<long long>());
        cnt = m;
    }

    long long extra = 0; // 被带走的书贡献的边际收益之和
    for (int i = 1; i <= cnt; i++) extra += diff[i];

    cout << base + extra << '\n';
    return 0;
}

复杂度

时间：读入与收集 $d_i$ 为 $O(n)$ ；nth_element 均摊 $O(n)$ ；求和为 $O(m)$ 。总 $O(n)$ （用排序实现则为 $O(n \log n)$ ，同样可过）。
空间： $O(n)$ ，三个 long long 数组约 12MB。

总结

碰到"每个元素两种选项、各带一个收益"的题，先找一个固定基准（这里是"全都不带走"），把选项差量化成单个边际收益，选择问题就变成了"挑最大的若干个正数"。名额是"最多"而不是"恰好"时，贪心只需要考虑正数；前 $m$ 大用 nth_element 或排序即可。注意收益可为负：答案可能是负数，比较和累加都要用 long long。

书

目录

形式化题目

思路

代码

复杂度

总结