书

GitHub跳转原题关系图返回列表

先默认全部不带走，每本书改带走只改变 d_i=a_i-b_i，问题变成从 n 个数里取至多 m 个正数使和最大。

OJ: roj

题目 ID: 20022

难度:入门

标签:贪心排序

创建: 2026-08-29 00:08

更新: 2026-10-07 13:50

后置题目
roj 1373鱼塘钓鱼(fishing）B 在枚举最远鱼塘、把每塘递减收益摊平成表之后，直接复用 A 教的「排序取前 m 大」这一贪心步骤，把它改成对各塘合并表降序取前 left 项求和；A 特有的基准转换 d_i=a_i-b_i 未被使用，故属模板级复用。luogu P9728[EC Final 2022] Dining ProfessorsA 教的是「每个元素两种选项各带收益时，先把选项差量化成单个边际收益，选择问题变成挑最大的若干个正数」；B 正是沿用这一步——先用贡献法把每道不辣菜在位置 p 的增益 c_p 算成独立的边际收益，再在「恰好选 n-a 个位置」的个数约束下取最大的若干项，B 另叠加的贡献法换序求 c_p 是 A 未教的新流程。

目录

  1. 题目描述
  2. 思路
  3. 参考代码

题目描述

小 W 要搬家，面前有 nn 本书，第 ii 本书带走的收益为 aia_i、不带走的收益为 bib_i，他最多能带走 mm 本书，求最大总收益。

输入：第一行 n,mn,m；第二行 nn 个整数 aia_i；第三行 nn 个整数 bib_i。输出一行一个整数表示最大收益。

样例输入 #1：2 1，a={5,4}a=\{5,4\}，b={3,6}b=\{3,6\}，输出 11。数据范围：0≤m≤n≤5×1050\le m\le n\le 5\times10^5，∣ai∣,∣bi∣≤109|a_i|,|b_i|\le 10^9。

思路

先默认全部不带走，基准为 ∑bi\sum b_i；第 ii 本书改为带走只带来边际变化 di=ai−bid_i=a_i-b_i。于是只需从正的 did_i 里挑不超过 mm 个最大的累加（di≤0d_i\le 0 的书不带走，名额不必用满），排序取前 mm 大即可，注意总和要用 long long。

参考代码

cpp
/**
 * 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-09-26 09:20
 */
// main.cpp：带走至多 m 本书，求最大总收益。
// 思路：基准转换——默认全部不带走（基准 = Σ b_i），
// 把第 i 本书改为带走只带来与其他书无关的变化 d_i = a_i - b_i，
// 所以只取 d_i > 0 的中最大的前 m 个累加。
// 做法：把正的 d_i 收集起来从大到小排序，再累加前 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 的书才值得带走
    }

    // 把正的边际收益按从大到小排序，收益大的书排前面
    sort(diff + 1, diff + cnt + 1, greater<long long>());

    // 名额只有 m 个，只累加最大的前 m 个
    if (cnt > m) cnt = m;

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

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