当前位置:   article > 正文

华为OD真题--分月饼--带答案_华为od机试真题-分月饼

华为od机试真题-分月饼

1. 华为OD机考题 + 答案

2023华为OD统一考试(A+B卷)题库清单-带答案(持续更新)

2023年华为OD真题机考题库大全-带答案(持续更新)

2. 面试题

一手真实java面试题:2023年各大公司java面试真题汇总--持续更新

3. 技术知识

java后端技术汇总 + 中间件 + 架构思想

题目描述:

公司分月饼,m个员工,买了n个月饼,m <= n,每个员工至少分一个月饼,但是也可以分到多个,单人分到最多月饼的个数是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

输出描述:

输出有多少种分法

示例1:

输入

2 4

输出

2

说明

4=1+3

4=2+2

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

示例2:

输入

3 5

输出

2

说明

5=1+1+3

5=1+2+3

示例3:

输入

3 12

输出

6

说明

满足要求的6种分法:

1、12 = 1 + 1 + 10 (Max1=10, Max2=1,不满足Max1-Max2 <= 3的约束)

2、12 = 1 + 2 + 9 (Max1=9,Max2=2,不满足Max1-Max2 <= 3的约束)

3、12 = 1 + 3 + 8 (Max1=8,Max2=3,不满足Max1-Max2 <= 3的约束)

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

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

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

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

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

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

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

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

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

  1. public class DivideMooncake {
  2. //非最优解,需要考虑减枝,减少遍历次数。
  3. public static void main(String[] args) {
  4. Scanner scanner = new Scanner(System.in);
  5. int [] num = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
  6. //分配人数
  7. int peoples = num[0];
  8. //待分配数量
  9. int dnum = num[1] - num[0];
  10. //重新分配后每个人月饼数量
  11. int [] nums = new int[peoples];
  12. // 用一个List来存储所有分配方案
  13. List<List<Integer>> result = new ArrayList<>();
  14. divide(dnum,peoples,nums,result);
  15. List<List<Integer>>filteredResult = removeDuplicate(result);
  16. //System.out.println(filteredResult);
  17. System.out.println(filteredResult.size());
  18. }
  19. public static void divide(int num,int peolpe, int [] nums,List<List<Integer>> result){
  20. if (peolpe == 1){
  21. nums[0] = num;
  22. List<Integer> allocation = new ArrayList<>();
  23. for (int i : nums){
  24. allocation.add(i);
  25. }
  26. result.add(allocation);
  27. return;
  28. }
  29. for (int i = 0; i <= num ; i++){
  30. //要分配的月饼
  31. nums[peolpe - 1] = i;
  32. //递归调用,将要分配的月饼分配给其它人
  33. divide(num - i,peolpe -1,nums,result);
  34. }
  35. }
  36. /**
  37. * 判断是否满足条件 Max(n) - Max(n-1) >= 3
  38. * @param nums
  39. * @return
  40. */
  41. public static Boolean satisfy(List<Integer> nums){
  42. int i = nums.size() -1;
  43. while (i >= 1){
  44. if (nums.get(i) - nums.get(i - 1) > 3){
  45. return false;
  46. }
  47. i--;
  48. }
  49. return true;
  50. }
  51. /**
  52. * 分数一致的去重
  53. * @param result
  54. * @return
  55. */
  56. public static List<List<Integer>> removeDuplicate(List<List<Integer>> result) {
  57. List<List<Integer>> filteredResult = new ArrayList<>();
  58. for (List<Integer> allocation : result) {
  59. boolean duplicate = false;
  60. allocation.sort(Integer::compareTo); // 对分配方案进行排序
  61. for (List<Integer> existingAllocation : filteredResult) {
  62. existingAllocation.sort(Integer::compareTo); // 对已有的分配方案进行排序
  63. if (Arrays.equals(existingAllocation.toArray(), allocation.toArray())) {
  64. duplicate = true; // 分配方案重复
  65. break;
  66. }
  67. }
  68. if (!duplicate) {
  69. if (satisfy(allocation)){
  70. filteredResult.add(allocation);
  71. }
  72. }
  73. }
  74. return filteredResult;
  75. }
  76. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家小花儿/article/detail/174257
推荐阅读
相关标签
  

闽ICP备14008679号