华为OD统一考试 - 分月饼

题目描述

中秋节,公司分月饼,m 个员工,买了 n 个月饼,m ≤ n,每个员工至少分 1 个月饼,但可以分多个,

  • 单人分到最多月饼的个数是 Max1 ,单人分到第二多月饼个数是 Max2 ,Max1 - Max2 ≤ 3 ,
  • 单人分到第 n - 1 多月饼个数是 Max(n-1),单人分到第n多月饼个数是 Max(n) ,Max(n-1) – Max(n) ≤ 3,

问有多少种分月饼的方法?

输入描述

每一行输入m n,表示m个员工,n个月饼,m ≤ n

输出描述

输出有多少种月饼分法

用例

输入

2 4

输出

2

说明

分法有2种:

4 = 1 + 3

4 = 2 + 2

注意:1+3和3+1算一种分法

输入

3 5

输出

2

说明

5 = 1 + 1 + 3

5 = 1 + 2 + 2

输入

3 12

输出

6

说明

满足要求的有6种分法:

12 = 1 + 1 + 10(Max1 = 10, Max2 = 1,不满足Max1 - Max2 ≤ 3要求)

12 = 1 + 2 + 9(Max1 = 9, Max2 = 2,不满足Max1 - Max2 ≤ 3要求)

12 = 1 + 3 + 8(Max1 = 8, Max2 = 3,不满足Max1 - Max2 ≤ 3要求)

12 = 1 + 4 + 7(Max1 = 7, Max2 = 4,Max3 = 1,满足要求)

12 = 1 + 5 + 6(Max1 = 6, Max2 = 5,Max3 = 1,不满足要求)

12 = 2 + 2 + 8(Max1 = 8, Max2 = 2,不满足要求)

12 = 2 + 3 + 7(Max1 = 7, Max2 = 3,不满足要求)

12 = 2 + 4 + 6(Max1 = 6, Max2 = 4,Max3 = 2,满足要求)

12 = 2 + 5 + 5(Max1 = 5, Max2 = 2,满足要求)

12 = 3 + 3 + 6(Max1 = 6, Max2 = 3,满足要求)

12 = 3 + 4 + 5(Max1 = 5, Max2 = 4,Max3 = 3,满足要求)

12 = 4 + 4 + 4(Max1 = 4,满足要求)

题目解析

本题类似于整数划分问题,即将一个正整数n,分解为m个正整数的方案数。

这类问题一般不会有太大的数量级,比如将10000分解为10个整数,那方案数就太多了。

本题给了一个限制条件,那就是,如果将分解后的m个正整数升序的话,相邻元素之间的差值不能超过3。

另外,分解方案不在意m个正整数的顺序,比如 1 2 1 和 1 1 2算一种方案。

我这里考虑使用分治递归求解。

分治递归可以想象成一棵树,这颗树有m层。

第0层相当于序号0个员工,该层有多个节点,每个节点的值即为序号0个员工可能分得的月饼数量。

  • 题目说,每个员工至少分得1个月饼,因此序号0个员工分得月饼数至少为1。
  • 为了保证不产生重复方案,因此我们默认当前求解的升序的m个正整数序列,因此序号0个员工分得的月饼数不能超过均值,即 n / m,因为一旦序号0个员工分得的月

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

2024华为OD机试卷题 文章被收录于专栏

本专栏给大家提供了华为2024最新华为OD 题目汇总。华为OD机试刷题记录机考算法题库,帮助你上岸华为。提供C++/Java、JavaScript、Python四种语言的解法。

全部评论

相关推荐

避坑恶心到我了大家好,今天我想跟大家聊聊我在成都千子成智能科技有限公司(以下简称千子成)的求职经历,希望能给大家一些参考。千子成的母公司是“同创主悦”,主要经营各种产品,比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司?没错,就是那种类型的公司。我当时刚毕业,急需一份临时工作,所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元,还包住宿,这吸引了我。面试的时候,HR也说了同样的话,感觉挺靠谱的。于是,我满怀期待地等待结果。结果出来后,我通过了面试,第二天就收到了试岗通知。试岗的内容就是地推销售,公司划定一个区域,然后你就得见人就问,问店铺、问路人,一直问到他们有意向为止。如果他们有兴趣,你就得摇同事帮忙推动,促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床,收拾后去公司,然后唱歌跳舞(销售公司都这样),7:55早课(类似宣誓),8:05同事间联系销售话术,8:15分享销售技巧,8:30经理训话。9:20左右从公司下市场,公交、地铁、自行车自费。到了市场大概10点左右,开始地推工作。中午吃饭时间大约是12:00,公司附近的路边盖饭面馆店自费AA,吃饭时间大约40分钟左右。吃完饭后继续地推工作,没有所谓的固定中午午休时间。下午6点下班后返回公司,不能直接下班,需要与同事交流话术,经理讲话洗脑。正常情况下9点下班。整个上班的一天中,早上到公司就是站着的,到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位,百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波,公司的投入成本几乎只有租金和工资,没有中央空调。早上2小时,晚上加班2小时,纯蒸桑拿。没有任何福利,节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思:新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数,类似传销模式,把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方,不能依墙而坐。早上吃早饭在公司外面的安全通道,未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候,带你的师傅会给你营造一个钱多事少离家近的工作氛围,吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之,大家在找工作的时候一定要擦亮眼睛,避免踩坑!———来自网友
qq乃乃好喝到咩噗茶:不要做没有专业门槛的工作
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务