田忌赛马 - 华为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的所有排列，然后统计满足条件的排列数量。

主要步骤：

1. 读取输入的数组a和b。
2. 初始化变量，包括数组长度n，最大满足条件的个数maxCnt，以及统计满足条件的排列数量resultCnt。
3. 使用递归进行排列组合的搜索，遍历a的所有排列，统计满足条件的个数和数量。
4. 输出结果。

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数组