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

题目描述

讨厌鬼的店铺要进 n 个货物,以及两个供货商 a 和 b ,第 i 件货物在 a 供货商处需要 a_i 元,在 b 供货商处需要 b_i 元。
讨厌鬼还有第三个选择就是在京东上网购,网购只能一次买齐 n 种货物,网购这 n 个货物的总价格为 x 元。
通过三种方式购买的 n 种货物都是一样的,可以在不同的供货商 a 和 b 处购买商品,我们的目标是需要买齐这 n 种货物。
讨厌鬼想知道,进这 n 个货物最少需要花多少元。

输入输出

输入描述
第一行输入两个整数 n,x(1≤ n ≤ 10^5,1 ≤ x ≤ 10^9) ,代表货物数量和网购总价格。
第二行输入 n 个整数 a_i(1 ≤ a_i ≤ 10^4 ),代表在a供应商处每件货物的价格。
第三行输入 n 个整数 b_i(1 ≤ b_i ≤ 10^4 ),代表在b供应商处每件货物的价格。
输出描述
一个整数,表示最少花钱数。

样例共 1 组

样例 1 · 显然网购更加划算。
输入
5 5
2 1 2 1 2
1 2 1 2 3
输出
5

算法解析依据充分

考点:数组 · 贪心

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

题目画像

  • 数据规模:n ≤ 1e5
  • 元素值域:x ≤ 1e9,a_i ≤ 1e4,b_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²) 会超时。
  • 元素值域最大到 1e9 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1:输入 5 5 / 2 1 2 1 2 / 1 2 1 2 3 → 输出 5

显然网购更加划算。

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

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

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