华为OD真题--分月饼--带答案

ゝ一纸荒年。 2023-10-14 22:59 167阅读 0赞

> 1. 华为OD机考题 + 答案
> 
> [2023华为OD统一考试（A+B卷）题库清单-带答案（持续更新）][2023_OD_A_B_-]
> 
> [2023年华为OD真题机考题库大全-带答案（持续更新）][2023_OD_-]
> 
> 2. 面试题
> 
> [一手真实java面试题：2023年各大公司java面试真题汇总--持续更新][java_2023_java_--]
> 
> 3. 技术知识
> 
> [java后端技术汇总 + 中间件 + 架构思想][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，满足要求）

public class DivideMooncake {
    //非最优解，需要考虑减枝，减少遍历次数。
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int [] num = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            //分配人数
            int peoples = num[0];
            //待分配数量
            int dnum = num[1] - num[0];
            //重新分配后每个人月饼数量
            int [] nums = new int[peoples];
            // 用一个List来存储所有分配方案
            List<List<Integer>> result = new ArrayList<>();
            divide(dnum,peoples,nums,result);
            List<List<Integer>>filteredResult = removeDuplicate(result);
    
            //System.out.println(filteredResult);
            System.out.println(filteredResult.size());
        }
    
        public static void divide(int num,int peolpe, int [] nums,List<List<Integer>> result){
            if (peolpe == 1){
                nums[0] = num;
                List<Integer> allocation = new ArrayList<>();
                for (int i : nums){
                    allocation.add(i);
                }
                result.add(allocation);
                return;
            }
    
            for (int i = 0; i <= num ; i++){
                //要分配的月饼
                nums[peolpe - 1] = i;
                //递归调用，将要分配的月饼分配给其它人
                divide(num - i,peolpe -1,nums,result);
            }
    
        }
    
        /**
         * 判断是否满足条件  Max(n) - Max(n-1) >= 3
         * @param nums
         * @return
         */
        public static Boolean satisfy(List<Integer> nums){
            int i = nums.size() -1;
            while (i >= 1){
                if (nums.get(i) - nums.get(i - 1) > 3){
                    return false;
                }
                i--;
            }
            return true;
        }
    
    
        /**
         * 分数一致的去重
         * @param result
         * @return
         */
        public static List<List<Integer>> removeDuplicate(List<List<Integer>> result) {
            List<List<Integer>> filteredResult = new ArrayList<>();
    
            for (List<Integer> allocation : result) {
                boolean duplicate = false;
                allocation.sort(Integer::compareTo); // 对分配方案进行排序
    
                for (List<Integer> existingAllocation : filteredResult) {
                    existingAllocation.sort(Integer::compareTo); // 对已有的分配方案进行排序
    
                    if (Arrays.equals(existingAllocation.toArray(), allocation.toArray())) {
                        duplicate = true; // 分配方案重复
                        break;
                    }
                }
    
                if (!duplicate) {
                    if (satisfy(allocation)){
                        filteredResult.add(allocation);
                    }
                }
            }
    
            return filteredResult;
        }
    
    }

[2023_OD_A_B_-]: https://blog.csdn.net/weixin_42450130/article/details/131750502
[2023_OD_-]: https://blog.csdn.net/weixin_42450130/article/details/131719081
[java_2023_java_--]: https://blog.csdn.net/weixin_42450130/article/details/131780683
[java_ _ _ _]: https://blog.csdn.net/weixin_42450130/article/details/132247441