华为OD刷题C卷 – 每日刷题 27（游戏分组，分配土地）

1、（游戏分组）：

这段代码是解决“游戏分组”的问题。它提供了一个Java类Main，其中包含main方法和getResult方法，以及一个辅助方法dfs，用于计算将10名游戏爱好者分为两队时，两队实力差绝对值的最小值。

main方法首先读取10名参与者的游戏水平评分，然后调用getResult方法并打印出分组后两组实力差绝对值的最小值。

getResult方法首先对评分进行升序排序，然后使用回溯算法的dfs方法来找出所有可能的5人组合及其战斗力之和。通过递归生成所有不重复的组合，并将它们的战斗力之和存储在ArrayList中。

dfs方法是一个递归函数，用于生成10名参与者的所有可能组合，并计算每个组合的战斗力之和。它通过遍历参与者并选择或不选择每个参与者来构建组合。

最后，getResult方法计算所有组合的战斗力之和与总战斗力之和的差异，并找出这些差异的最小值。

2、（分配土地）：

这段代码是解决“分配土地”的问题。它提供了一个Java类Main，其中包含main方法和一个内部类Rect，用于计算给定数字在矩阵中所占的最大矩形面积。

main方法首先读取矩阵的行数和列数，然后使用一个HashMap来存储每个数字的最小和最大行坐标以及最小和最大列坐标。通过遍历矩阵，更新每个数字的坐标范围。

Rect内部类用于记录每个数字的坐标范围，并提供方法来更新这些坐标。

最后，main方法遍历HashMap中的所有条目，计算每个数字所占的最大矩形面积，并找出所有矩形面积中的最大值。

package OD349;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
/**
* @description 游戏分组
* @level 7
* @score 100
* @type 回溯算法
*/
/**
* 题目描述
* 部门准备举办一场王者荣耀表演赛，有 10 名游戏爱好者参与，分为两队，每队 5 人。
* 

* 每位参与者都有一个评分，代表着他的游戏水平。为了表演赛尽可能精彩，我们需要把 10 名参赛者分为示例尽量相近的两队。
* 

* 一队的实力可以表示为这一队 5 名队员的评分总和。
* 

* 现在给你 10 名参与者的游戏水平评分，请你根据上述要求分队，最后输出这两组的实力差绝对值。
* 

* 例：10 名参赛者的评分分别为：5 1 8 3 4 6 7 10 9 2，分组为（1 3 5 8 10）和（2 4 6 7 9），两组实力差最小，差值为1。有多种分法，但是实力差的绝对值最小为1。
* 

* 输入描述
* 10个整数，表示10名参与者的游戏水平评分。范围在 [1, 10000] 之间。
* 

* 输出描述
* 1个整数，表示分组后两组实力差绝对值的最小值。
*/
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//10名玩家的评分
int[] scores = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
System.out.println(getResult(scores));
}
//找到两队游戏水平最小绝对值差值
public static int getResult(int[] scores) {
//先按升序排序
Arrays.sort(scores);
//存放所有5人组合可能的战斗力之和
ArrayList<Integer> res = new ArrayList<>();
//dfs求10选5的去重组合，并将5人战斗力之和加入res
dfs(scores, 0, 0, 0, res);
//战斗力总和
int sum = Arrays.stream(scores).sum();
//res 中存放的是所有5人战斗力的集合，假如1队战斗力为sum1,另一队战斗力就是sum-sum1 差值的绝对值就是Math.abs(sum-2*sum1)
//然后求差值的最小值
return res.stream().map(sum1 -> Math.abs(sum - 2 * sum1)).min((a, b) -> a - b).orElse(0);
}
/**
* 10选5去重组合，并将5人组合的战斗力之和加入res
*
* @param scores 战斗力数组
* @param index  开始的下标
* @param level  树的层级
* @param sum    当前的战斗力之和
* @param res    存放结果
* @return void
* @create 2024/3/23 15:30
*/
public static void dfs(int[] scores, int index, int level, int sum, ArrayList<Integer> res) {
//返回上一层标记，当level=5时，则已经添加了5人
if (level == 5) {
res.add(sum);
return;
}
//没满5人，则添加，如果战斗力一样则去重
for (int i = index; i < scores.length; i++) {
//遍历到i后面的时候，如果跟前一个人战斗力一样，则去重，因为最后res求的是总和
if (i > index && scores[i] == scores[i - 1]) {
continue;
}
dfs(scores, i + 1, level + 1, sum + scores[i], res);
}
}
}

package OD350;
import java.util.HashMap;
import java.util.Scanner;
/**
* @description 分配土地
* @level 3
* @type 逻辑分析
*/
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
//静态类，记录每个数字的最小最大坐标
static class Rect {
int minRow = Integer.MAX_VALUE;
int maxRow = Integer.MIN_VALUE;
int minCol = Integer.MAX_VALUE;
int maxCol = Integer.MIN_VALUE;
/*
* 更新该数字最大最小横坐标
* @create 2024/3/9 23:11
* @param row
* @return void
*/
private void setRow(int row){
this.minRow = Math.min(this.minRow,row);
this.maxRow = Math.max(this.maxRow,row);
}
/*
* 更新该数字的最大最小纵坐标
* @create 2024/3/9 23:12
* @param col
* @return void
*/
private void setCol(int col){
this.minCol = Math.min(this.minCol,col);
this.maxCol = Math.max(this.maxCol,col);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()){
//几行
int m = sc.nextInt();
//几列
int n = sc.nextInt();
HashMap<Integer,Rect> map = new HashMap<>();
for (int i =0;i<m;i++){
for (int j = 0;j<n;j++){
int num = sc.nextInt();
if (num>0){
//若没有该num则新建一个Rect对象，修改当前数字所表示的最大最小坐标
map.putIfAbsent(num,new Rect());
map.get(num).setRow(i);
map.get(num).setCol(j);
}
}
}
int maxArea = 0;
//遍历
for (int num : map.keySet()){
//Rect rect = map.get(num);
//maxArea = Math.max(maxArea,(rect.maxRow-rect.minRow+1)*(rect.maxCol-rect.minCol+1));
maxArea = Math.max(maxArea, (map.get(num).maxRow - map.get(num).minRow + 1) * (map.get(num).maxCol - map.get(num).minCol + 1));
}
System.out.println(maxArea);
}
}
}