讨厌鬼的店铺要进 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供应商处每件货物的价格。
一个整数,表示最少花钱数。
5 5 2 1 2 1 2 1 2 1 2 3
5
考点:数组 · 贪心
数据规模 n ≤ 1e5 | 限制 1 秒 / 256MB | 标准输入输出
推荐方向:贪心
每一步都取当前最优,靠问题性质保证局部最优能拼成全局最优。
思路框架(贪心 通法 · 非本题专属)
实现要点:贪心题关键在于排序规则:按什么关键字排序决定了策略是否正确。
复杂度:时间 O(n log n)(含排序) | 空间 O(1) ~ O(n)
该范式的通法易错点
对照本题
样例 1:输入 5 5 / 2 1 2 1 2 / 1 2 1 2 3 → 输出 5
显然网购更加划算。
解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:2023年秋招-京东-技术通用岗位-第四批笔试。