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

本文主要是介绍华为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 人。* <p>* 每位参与者都有一个评分，代表着他的游戏水平。为了表演赛尽可能精彩，我们需要把 10 名参赛者分为示例尽量相近的两队。* <p>* 一队的实力可以表示为这一队 5 名队员的评分总和。* <p>* 现在给你 10 名参与者的游戏水平评分，请你根据上述要求分队，最后输出这两组的实力差绝对值。* <p>* 例：10 名参赛者的评分分别为：5 1 8 3 4 6 7 10 9 2，分组为（1 3 5 8 10）和（2 4 6 7 9），两组实力差最小，差值为1。有多种分法，但是实力差的绝对值最小为1。* <p>* 输入描述* 10个整数，表示10名参与者的游戏水平评分。范围在 [1, 10000] 之间。* <p>* 输出描述* 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人战斗力之和加入resdfs(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);}}
}