OPPO · 贪心 · 算法编程题
OPPO 贪心 时限 1 秒 / 256 MB

题目描述

小O有三盒糖果，糖果数分别为 a,b 和 c 。
现在小O又有了 x 颗糖果，他要把这 x 颗糖果恰好分到新的 k 个盒子里面去，保证每一个盒子里至少有一颗糖果。这样他就拥有了 k+3 盒糖果，然后他会在这 k+3 盒糖果中挑选出最多的那一盒糖果。
显然， x 颗糖果分到 k 个盒子里往往不止一种方案。小O想知道，无论他如何分配这 x 颗糖果，糖果最多的那一个盒子的编号是否确定且唯一。

输入输出

输入描述
第一行输入三个整数 a,b 和 c(1≤ a,b,c ≤ 10^9 ) 表示初始三盒糖果的个数。
第二行输入两个整数 x 和 k( 1≤ k ≤ x ≤ 10^9 ) 代表小O新获得的糖果个数，和需要新放入糖果的盒子数。
输出描述
如果糖果最多的那一个盒子的编号确定且唯一，输出“ YES ”
，否则，输出“ NO ”。

样例共 2 组

样例 1
输入
4 2 3
2 2
输出
YES
样例 2
输入
5 3 6
100 2
输出
NO

算法解析依据充分

考点：贪心 · 基础数学

限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 元素值域：a ≤ 1e9，b ≤ 1e9，c ≤ 1e9（注意整数类型选择，避免溢出）
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：贪心

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

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

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

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

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

该范式的通法易错点

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

对照本题

  • 元素值域最大到 1e9 —— 求和 / 相乘时记得开 64 位整数。

样例

样例 1

  • 输入：4 2 3 / 2 2
  • 输出：YES

样例 2

  • 输入：5 3 6 / 100 2
  • 输出：NO

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

本题来源：2024年秋招-OPPO-移动开发笔试。

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