华为OD刷题C卷 - 每日刷题 26（学生重新排队，分月饼）_华为od 学生重新排队

1、（学生重新排队）：

这段代码是解决“学生重新排队”的问题。它提供了一个Java类Main，其中包含main方法和getResult方法，以及一个内部类Block，用于计算老师最少需要调整多少次队伍，才能让同组学生彼此相连。

main方法首先读取学生目前的排队情况和随机抽签分组情况，然后调用getResult方法并打印所需的最小调整次数。

getResult方法首先将学生分组情况转换为组号，并使用一个链表queue来维护当前队伍中学生的组分布。通过模拟调整过程，代码计算出将学生调整到同组相连所需的最少步数。这个过程涉及到合并连续相同组的学生（即"连连看"），并计算移动学生所需的步数。

confirm方法用于删除链表中特定组号的学生，并合并剩余的组。

2、（分月饼）：

这段代码是解决“分月饼”的问题。它提供了一个Java类Main，其中包含main方法和getResult方法，用于计算在给定条件下分月饼的方法数。

main方法首先读取员工数m和月饼数n，然后调用getResult方法并打印总方案数。

getResult方法使用递归的方式，尝试每一种可能的月饼分配方案。递归的终止条件是当只剩下一个员工或者分配的月饼数不足以继续分配时。方法中使用了参数min和max来控制当前员工分配的月饼数量范围，以及remain来记录剩余的月饼数。

package OD347;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * @description 学生重新排队
 * @level 9
 * @score 200
 * @url https://hydro.ac/d/HWOD2023/p/OD347
 */
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    //分块：即连续的相同组的小朋友个数
    static class Block {
        //组号
        int groupId;
        //连续的人数[1,3]
        int count;

        //默认初始化
        public Block(int groupId, int count) {
            this.groupId = groupId;
            this.count = count;
        }
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        //初始化排队顺序
        int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = nums.length;

        //序号 -> 组号的对应关系

        int[] group = new int[n + 1];
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            //每三个为一组 整除3
            group[num] = i / 3;
        }

        //输出最多需要排多少次
        System.out.println(getResult(nums, group));

    }

    /**
     * 按组调整需要的最小调整次数
     *
     * @param nums
     * @param group
     * @return int
     */
    public static int getResult(int[] nums, int[] group) {
        //相邻相同组号合并
        LinkedList<Block> queue = new LinkedList<>();

        for (int num : nums) {
            int groupId = group[num];
            //如果与上一个组号不同，则新加入
            if (queue.isEmpty() || queue.getLast().groupId != groupId) {
                queue.addLast(new Block(groupId, 1));
            } else {
                //与前一个组号相同
                queue.getLast().count++;
            }
        }
        //此时queue中形如：[11][222][33][1][3]

        //记录调整次数
        int moved_count = 0;
        //每遇到一个相同组号且个数为3时，消去，类似于连连看，最后队列清空
        while (!queue.isEmpty()) {
            Block first = queue.removeFirst();

            //如果第一组只有一个连续的人，如
            // 1 x[] 1 1 y z
            // 1 x[] 1 y 1 z
            if (first.count == 1) {
                Block x = queue.getFirst();
                //如果x是完整组，则消去，且不消耗步数
                while (x.count == 3) {
                    queue.removeFirst();
                    x = queue.getFirst();
                }

                //如果现在x与first刚好是同组，且加起来是3个人，则消去，步数+1，相当于把first插入到x[11]前面
                if (x.groupId == first.groupId && x.count + first.count == 3) {
                    moved_count++;
                    queue.removeFirst();
                } else {
                    // 情况如下：中间间隔其他组
                    // 1 x[2 2] 1 1
                    // 1 x[2] 1 2 1
                    // 将后面的两个1移动到开头
                    moved_count += 2;

                    //删去first.groupId后，合并剩下组
                    queue = confirm(queue, first.groupId);
                }
            } else if (first.count == 2) {
                // 当first.count == 2 时，情况如下：
                // 1 1 x 1 y z
                //把后面的那个1拿到前面来
                moved_count++;
                //删去first.groupId后，合并剩下组
                queue = confirm(queue, first.groupId);
            }
            //first.count = 3 则不需要操作，直接被removeFirst()，开始下一组

        }
        //返回操作次数
        return moved_count;
    }

    /**
     * 把queue中组号为confirmed_groupId的删去后合并剩下的组
     *
     * @param queue
     * @param confirmed_groupId
     * @return java.util.LinkedList<OD347.Main.Block>
     */
    public static LinkedList<Block> confirm(LinkedList<Block> queue, int confirmed_groupId) {
        LinkedList<Block> back_queue = new LinkedList<>();
        while (!queue.isEmpty()) {
            Block first = queue.removeFirst();

            if (first.groupId == confirmed_groupId) {
                continue;
            }
            if (back_queue.isEmpty() || back_queue.getLast().groupId != first.groupId) {
                //添加新的
                back_queue.addLast(new Block(first.groupId, first.count));
            } else {
                //次数加1
                back_queue.getLast().count += first.count;
            }
        }

        return back_queue;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

package OD348;

import java.util.Scanner;

/**
 * @description 分月饼
 * @level 7
 * @score 200
 */

/**
 * 题目描述
 * 中秋节，公司分月饼，m 个员工，买了 n 个月饼，m ≤ n，每个员工至少分 1 个月饼，但可以分多个，
 * <p>
 * 单人分到最多月饼的个数是 Max1 ，单人分到第二多月饼个数是 Max2 ，Max1 - Max2 ≤ 3 ，
 * 单人分到第 n - 1 多月饼个数是 Max(n-1)，单人分到第n多月饼个数是 Max(n) ，Max(n-1) – Max(n) ≤ 3,
 * 问有多少种分月饼的方法？
 * <p>
 * 输入描述
 * 每一行输入m n，表示m个员工，n个月饼，m ≤ n
 * <p>
 * 输出描述
 * 输出有多少种月饼分法
 */
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    //月饼个数
    static int n;
    //员工数
    static int m;
    //最大差值
    static int maxDiff = 3;
    //方案个数
    static int ans = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //员工
        m = sc.nextInt();
        //月饼
        n = sc.nextInt();
        //如果只有一个员工

        getResult(0, 1, n / m, n);

        System.out.println(ans);
    }

    /**
     * 递归判断分月饼的总方案数
     *
     * @param index  当前员工编号
     * @param min    当前员工分的最少个数
     * @param max    当前员工分的最大个数
     * @param remain 分给当前员工前，还剩的月饼个数
     * @return boolean
     * @create 2024/3/20 13:52
     */
    public static void getResult(int index, int min, int max, int remain) {
        //如果只有一个人，就只有一种分法
        if (m == 1) {
            ans = 1;
            return;
        }

        //结束递归条件：最后一个分的月饼与上一个分的月饼相差小于3 因为去重控制，每一个员工的min值就是上一个员工分的月饼数量
        if (index == m - 1) {
            if (remain - min <= maxDiff) {
                ans++;
            }
            //返回上层递归
            return;
        }

        //分月饼：每个位置都有max-min种分法，且因为控制递归，所有每个人的max不能超过剩下月饼平均分配的数量
        //如果超过了平均数量，后面就一定会有人分的比第i个人少
        for (int i = min; i <= max; i++) {
            //把i个月饼分给当前员工
            remain -= i;
            //看后面是否能成功递归
            getResult(index + 1, i, Math.min(i + maxDiff, remain / (m - index - 1)), remain);
            //不管上一步能否最终分发完，i+1，开始下一轮递归
            remain += i;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86