贝壳找房 · 贪心 · 算法编程题
贝壳找房 贪心 T ≤ 1e3 时限 1 秒 / 64 MB

题目描述

初始有两个长度均为 m 的数组 a_ 1, a_ 2,..., a_ m 和 b_ 1, b_ 2,..., b_ m .
牛牛想在其中选出 n 个数求和，选数的规则如下：
1. 每个 a 数组中的数只能被选择一次，而每个 b 数组中的数可以被选择无数次。
2. 想要选择 b 数组中的数，就必须先选择 a 数组中相同下标的数。例如：想要选择 b_ i ，就必须先选择 a_ i .
在上述规则下，最终选出的 n 个数求和的最大值是多少？

输入输出

输入描述
第一行输入一个正整数 T( 1≤ T≤ 1000) ，代表测试数据组数。
对于每组测试数据，第一行输入两个正整数 n, m( 1≤ n≤ 10 ^ 9; 1≤ m≤ 1000) ，依次代表需要找 n 个数求和以及 a, b 数组的长度。
接下去 m 行，每行两个正整数 a_ i, b_ i( 1≤ a_ i, b_ i≤ 10 ^ 9) .
输出描述
对于每组测试数据，一行输出一个正整数代表答案。

样例共 1 组

样例 1 · 选择 a_ 1, a_ 2 以及四次 b_ 2 ，可以达到 6+ 1+ 4× 6= 31 ，同时，其它选数方案求得的和，一定不会超过 31 .
输入
1
6 3
6 0
1 6
4 3
输出
31

算法解析依据充分

考点：贪心

数据规模 T ≤ 1e3 ｜ 限制 1 秒 / 64MB ｜ 标准输入输出

题目画像

  • 数据规模：T ≤ 1e3，m ≤ 1e3
  • 元素值域：n ≤ 1e9，i ≤ 1e9（注意整数类型选择，避免溢出）
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：贪心

本题切入点

b 数组的元素可以无限取但必须先选对应 a；按 a+b 从大到小排序，优先用「门槛低、收益高」的组合填满 n 个数。

每一步都取当前最优，靠问题性质保证局部最优能拼成全局最优。

思路框架（贪心 通法 · 非本题专属）

  1. 找出「局部最优怎么选」（往往与排序后的顺序有关）。
  2. 论证（或理性相信）这个贪心策略不会被反例击破：常用交换论证法。
  3. 按策略一次扫描（通常要先排序）得到答案。
  4. 若贪心无法证明，考虑改用 DP（贪心的反例通常来自「当前最优影响后续选择」）。

实现要点：贪心题关键在于排序规则：按什么关键字排序决定了策略是否正确。

复杂度：时间 O(n log n)（含排序） ｜ 空间 O(1) ~ O(n)

该范式的通法易错点

  • 策略不成立却当成贪心做（典型错因）。
  • 排序关键字选错，或相同关键字时的次级规则没考虑。

对照本题

  • 数据规模 T ≤ 1e3，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 元素值域最大到 1e9 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 1 / 6 3 / 6 0 / 1 6 / 4 3 → 输出 31

选择 a_ 1, a_ 2 以及四次 b_ 2 ，可以达到 6+ 1+ 4× 6= 31 ，同时，其它选数方案求得的和，一定不会超过 31 .

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：贝壳找房2023届校招开发类试卷。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解