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 满足要求)文章来源:https://www.toymoban.com/news/detail-659206.html
12 = 4 + 4 + 4 (Max1=4,满足要求)文章来源地址https://www.toymoban.com/news/detail-659206.html
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;
}
}
到了这里,关于华为OD真题--分月饼--带答案的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!