华为od-C卷200分题目

华为od-C卷200分题目 - 1分月饼

题目描述

中秋节，公司分月饼，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

输出描述
输出有多少种月饼分法

示例1
输入：
2 4

输出：
2

说明：
分法有2种
4=1+3
4=2+2
注意:1+3和3+1算一种分法
示例2
输入：
3 5

输出：
2

说明：
5=1+1+3
5=1+2+2
示例3
输入：
3 12

输出：
6

说明：
满足要求的有6种分法:
12=1+1+10(Max1=10,Max2=1，不满足要求)
12=1+2+9(Max1=9,Max2=2,不满足要求)
12=1+3+8(Max1=8,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,满足要求)

题解

    import java.util.LinkedList;
    import java.util.Scanner;
    
    public class Main {
        static LinkedList<Integer> list;
        static int res;
        static int n, m, base;
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            n = sc.nextInt();
            m = sc.nextInt();
            if(n == 1 ) {
                System.out.println(1);
                return;
            }
            base = 1;  
            int least = 3 * n * (n - 1) / 2;  
            while (base * n + least < m) {
                base++;
            }
    
            list = new LinkedList<>();
            res = 0;
            distribution(0, m);
            System.out.println(res);
        }
    
        public static void distribution(int index, int sum) {
            if (index == n - 1) {
                // 前一个树和最后一个数的差值不能超过3，最后一个数不能为负
                if (sum >= 0 && sum <= list.get(index - 1) + 3) {
                    res++;
                }
                return;
            }
            int last, end;
            if (index == 0) {
                last = base;        // 如果是第一个数，则从保底开始
                end = sum / n;        // 第一个数最大为平均分配的大小
            }else {
                last = list.get(index - 1); //不是第一个数则从前一个数的最大值
                end = Math.min(last + 3, sum / (n - index));
             // 最大值为剩下的人平均分配的平均数和上个数最大值加三中的最小值
            }
            for (int i = last;i<= end;i++ ) {
                list.add(i);
                distribution(index + 1, sum - i);
                list.remove(index);
            }
        }
    
    }