田忌赛马 - 华为OD统一考试(C卷)
OD统一考试(C卷)
分值: 200分
题解: Java / Python / C++
题目描述
给定两个只包含数字的数组a,b,调整数组a里面数字的顺序,使得尽可能多的a[i] > b[i]。
数组a和b中的数字各不相同。输出所有可以达到最优结果的a数组数量。
输入描述
输入的第一行是数组a中的数字,其中只包含数字,每两个数字之间相隔一个空格,a数组大小不超过10
输入的第一行是数组b中的数字,其中只包含数字,每两个数字之间相隔一个空格,b数组大小不超过10
输出描述
输出所有可以达到最优结果的a数组数量
示例1
输入:
11 8 20
10 13 7
输出:
1
说明:
最优结果只有一个,a=[11,20,8] ,故输出 1 。
示例2
输入:
11 12 20
10 13 7
输出:
2
说明:
有两个 a 数组的排列可以达到最优结果, [12,20,11] 和 [11,20,12] ,故输出 2 。
题解
题目要求调整数组a中数字的顺序,使得尽可能多的a[i] > b[i]。可以通过穷举a的所有排列,然后统计满足条件的排列数量。
主要步骤:
- 读取输入的数组a和b。
- 初始化变量,包括数组长度n,最大满足条件的个数maxCnt,以及统计满足条件的排列数量resultCnt。
- 使用递归进行排列组合的搜索,遍历a的所有排列,统计满足条件的个数和数量。
- 输出结果。
Java
import java.util.Arrays;
import java.util.Scanner;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[] a = Arrays.stream(in.nextLine().split(" "))
.mapToInt(Integer::parseInt).toArray();
int[] b = Arrays.stream(in.nextLine().split(" "))
.mapToInt(Integer::parseInt).toArray();
Solution solution = new Solution(a, b);
solution.solve(0, 0);
System.out.println(solution.resultCnt);
}
}
class Solution {
int[] a, b;
int n, maxCnt, resultCnt;
boolean[] vis;
public Solution(int[] a, int[] b) {
this.a = a;
this.b = b;
this.n = a.length;
this.maxCnt = 0;
this.resultCnt = 0;
this.vis = new boolean[n];
}
void solve(int idx, int cnt) {
// 剪枝:找不到最优结果a数组
if (n - idx + cnt < maxCnt) return;
// 所有数字排列完
if (idx == n) {
if (cnt > maxCnt) { // 找到更优的结果a数组
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2024华为OD机试真题题解 文章被收录于专栏
华为OD机考(C卷、D卷)算法题库(绝对都是原题),帮助你上岸华为(已经不少小伙伴成功上岸)。提供Java、Python、C++ 三种语言的解法。每篇文章都有详细的解题步骤、代码注释详细及相关知识点的练习题。有问题,随时解答。 从 2024年4月24开始,考的都是华为OD统一考试(D卷),据已经参加D卷考试的同学反馈D卷和C卷是一样的,如果发现新题会及时更新。