京东 · 贪心 · 算法编程题
京东 贪心 n ≤ 1e5 时限 1 秒 / 256 MB

题目描述

小红需要 n 个不同的魔法药剂，她可以从商店以 a_i 的价格购买第 i 种红色版本魔法药剂，也可以用两种其他的红色版本药剂配置蓝色版本。
小红想知道，她最少需要花多少钱才能得到 1 到 n 个不同的魔法药剂，蓝色或者红色都可以。

输入输出

输入描述
第一行输入一个整数 n ，表示魔法药剂数量。
第二行输入 n 个整数 a_i ，表示第 i 种红色版本魔法药剂的价格。
接下来 n 行，每行两个整数 b_i 和 c_i ，表示用第 b_i 种和第 c_i 种红色版本魔法药剂配置第 i 种蓝色版本魔法药剂。
1 ≤ n ≤ 10^5
1 ≤ a_i ≤ 10^4
1 ≤ b_i, c_i ≤ n
输出描述
输出一个整数，表示最少需要花多少钱才能得到 1 到 n 个不同的魔法药剂，蓝色或者红色都可以。

样例共 1 组

样例 1 · 红色药剂的价格分别为 [2, 4, 10, 1, 3] 蓝色药剂的价格分别为 [14, 4, 6, 7, 3] 配置第三种蓝色药剂，其他都购买红色药剂，花费 16。
输入
5
2 4 10 1 3
2 3
4 5
1 2
2 5
1 4
输出
16

算法解析依据充分

考点：数组 · 贪心

数据规模 n ≤ 1e5 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 1e5
  • 元素值域：a_i ≤ 1e4（注意整数类型选择，避免溢出）
  • 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：贪心

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

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

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

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

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

该范式的通法易错点

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

对照本题

  • 数据规模 n ≤ 1e5，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 元素值域最大到 1e4 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 5 / 2 4 10 1 3 / 2 3 / 4 5 / 1 2 / 2 5 / 1 4 → 输出 16

红色药剂的价格分别为 [2, 4, 10, 1, 3]

蓝色药剂的价格分别为 [14, 4, 6, 7, 3]

配置第三种蓝色药剂，其他都购买红色药剂，花费 16。

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

本题来源：2023年秋招-京东-技术通用岗位-第七批笔试。

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