小O的糖果
小O的糖果
OPPO 笔试真题 · 2024 秋招 · 移动开发
判题请到牛客原题提交。
题目描述
小O有三盒糖果,糖果数分别为 和 。
现在小O又有了 颗糖果,他要把这 颗糖果恰好分到新的 个盒子里面去,保证每一个盒子里至少有一颗糖果。这样他就拥有了 盒糖果,然后他会在这 盒糖果中挑选出最多的那一盒糖果。
显然, 颗糖果分到 个盒子里往往不止一种方案。小O想知道,无论他如何分配这 颗糖果,糖果最多的那一个盒子的编号是否确定且唯一。
输入格式
第一行输入三个整数 和 表示初始三盒糖果的个数。
第二行输入两个整数 和 代表小O新获得的糖果个数,和需要新放入糖果的盒子数。
输出格式
如果糖果最多的那一个盒子的编号确定且唯一,输出“”
,否则,输出“”。
示例
示例 1
输入:
4 2 3
2 2输出:
YES示例 2
输入:
5 3 6
100 2输出:
NO解题思路
第一步:先分清「哪些盒子的数量是固定的」
- 三盒原有的糖果数是固定的,编号 1、2、3;
- 新盒子有 个(编号 ),装多少完全取决于分配方案。
记原有三盒的最大值为 ,再记取到 的盒数为 ( 可以是 1、2、3)。
题目问的是「糖果最多的那一盒的编号是否确定且唯一」。所以关键不是最多
有多少颗,而是这个「最多」会落在哪个编号上。
第二步:新盒子能取到的范围
颗糖恰好分进 个盒子、每盒至少 1 颗,所以一个盒子最多拿
颗——其它 个盒子各留 1 颗,剩下的全给它。这个上界是能真正取到的。
还有一个很重要的事实:只要 ,取值 中的任何一个数,
既可以放在 4 号盒,也可以放在 5 号盒。新盒子之间是对称的,这正是
「编号不确定」的来源。
第三步:分三种情况讨论
| 情况 | 会发生什么 | 结论 |
|---|---|---|
| , | 最大的一堆可以放 4 号盒,也可以放 5 号盒 | NO |
| , | 只有一个新盒子,它必然装 颗,编号固定是 4 | YES |
| 可以让某个新盒子也拿到 ,与原最大值并列 | NO | |
| 且 | 新盒子全都比 小,最多的一定是原来那盒 | YES |
| 且 | 原来的两盒并列最多 | NO |
注意到 时 ,所以「 且 」这一行同样覆盖了
「只有一个新盒子、而且它比原最大值小」的情形。
完整代码实现
import sys
def solve() -> None:
"""比较「原有最大值」与「新盒子可能的最大值」,分情况判断"""
data = sys.stdin.buffer.read().split()
if not data:
return
a, b, c = int(data[0]), int(data[1]), int(data[2])
x, k = int(data[3]), int(data[4])
m = max(a, b, c)
cnt_m = (a == m) + (b == m) + (c == m) # 有几盒并列最大
top = x - k + 1 # 单个新盒子最多能装多少
if k == 1 and x > m:
# 只有一个新盒子,它必然就是最多的那一盒,编号确定为 4
ans = True
elif top < m and cnt_m == 1:
# 新盒子全都比 m 小,且原来最大的那盒唯一
ans = True
else:
ans = False
sys.stdout.write(("YES" if ans else "NO") + "\n")
if __name__ == "__main__":
solve()示例推演
示例 1:a = 4, b = 2, c = 3, x = 2, k = 2
、,。
分配方案只有一种:两个新盒子各 1 颗。于是五盒是
| 编号 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 糖果 | 4 | 2 | 3 | 1 | 1 |
最多的是 1 号盒,而且无论怎么分(这里只有一种分法)都是它,输出 YES。
这也符合判断:「 且 」。
示例 2:a = 5, b = 3, c = 6, x = 100, k = 2
、,且 。
| 分配方案 | 五盒糖果 | 最多的是 |
|---|---|---|
| 99 + 1 | 5, 3, 6, 99, 1 | 4 号盒 |
| 1 + 99 | 5, 3, 6, 1, 99 | 5 号盒 |
两种方案都合法,最多盒的编号却不同,输出 NO。
再看两个边界
a = 5, b = 3, c = 6, x = 7, k = 2:。取分配
,得到5, 3, 6, 6, 1,3 号盒和 4 号盒并列最多,编号不唯一,
输出NO。a = 1, b = 1, c = 1, x = 2, k = 1:,唯一的新盒子装 2 颗,
四盒是1, 1, 1, 2,最多的是 4 号盒,输出YES。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 公式分类讨论(本文) | 只要最大值、最大值个数、新盒子上界三个数 | ||
| 枚举所有分配方案 | — | 到 ,方案数量天文数字,不可行 |
易错点总结
1. 把 算成平均值
是「尽量平均分时每盒的数量」,不是上界。真正的上界是
:其它盒子各留 1 颗,剩下的全给同一个盒子。
2. 忘记「每盒至少一颗」
上界写成 就会漏掉 颗的预留,导致 偏大,答案偏向 NO。
3. 把 判成 YES
只要新盒子能追平原最大值,就存在一种分配让「最多」并列,编号不唯一。
判断要用严格小于:top < m。
4. 忽略 的特殊性
只有一个新盒子时,它装多少是确定的( 颗),编号也就确定。此时哪怕
比原最大值大,答案也是 YES。这是唯一一个「新盒子成为最大值仍然确定」
的情形。
5. 忘记检查原最大值是否唯一
a = 10, b = 10, c = 3 时,即使新盒子都很小,最多的也有两个并列,编号
不确定,答案是 NO。
6. 把「编号」当成「数值」
题目问的是编号是否确定且唯一,不是最多有多少颗糖。两盒并列最多时,
「最多」的数值是确定的,但编号不是。
扩展思考
- 如果改成问「最多那一盒的糖果数可能是多少」,答案是一个区间:
最小值是 (尽量平均分),
最大值是 (尽量集中)。 - 把三盒原有糖果换成 盒,结论完全一样,只需要 和 出现的次数,
这就是「只保留关键统计量」的典型例子。 - 如果没有「每盒至少一颗」的限制(允许空盒),上界就变成 ,其它结论不变。
- 如果允许新盒子的数量也由小O决定( 不固定),那么只要 就能
让新盒子的值任意大,除了原有最大值唯一且「不许新盒子超过它」这类附加
条件下,答案基本恒为 NO。