[华为OD] C卷 田忌赛马 DFS 200

题目：

给定两个只包含数字的数组a, b,调整数组a里面数字的顺序，使得尽可能多的a[i] >b[i]。

数组a和b中的数字各不相同。

输出所有可以达到最优结果的a数组的数量

输入描述

输入的第一行是数组a中的数字，其中只包含数字，每两个数字之间相隔一个空格，a数组大 

小不超过10

输入的第二行是数组b中的数字，其中只包含数字，每两个数字之间相隔一个空格，b数组大 

小不超过10

输出描述

输出所有可以达到最优结果的a数组数量

示例1：

输入：

11 8 20

10 137

输出：

1

说明：

最优结果只有一个，a =[11,20,8],故输出1

示例2：

输入：

11 12 20

10 13 7

输出： 

2

说明：

有两个a数组的排列可以达到最优结果［ 12,20,11］ 和[11,20,12］ ,故输出2。

题解：

首先最优解。这个可以参考letcode这个题目：. - 力扣（LeetCode）

田忌赛马。

这边因为数组大小不超过10，所以可以采用DFS暴利解法，把所有的数据都拿到比较，然后找出最优解的个数就可以了。

关于DFS，可以看下这个视频，就能理解了。dfs(迷宫求解代码实现）_哔哩哔哩_bilibili

代码

import java.util.*;
 
public class OverCountNum {
    private static Map<Integer, Integer> countMap = new HashMap<>();
    private static List<Integer> countList = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        String aNumString[] = sc.nextLine().split(" ");
        String bNumString[] = sc.nextLine().split(" ");
 
        int aNum[] = new int[aNumString.length];
        int bNum[] = new int[bNumString.length];
        int aLength = aNumString.length;
        int bLength = bNumString.length;
 
        int visit[] = new int[aLength];
        for (int i = 0; i < aLength; i++) {
            aNum[i] = Integer.valueOf(aNumString[i]);
            visit[i] = 0;
        }
 
        for (int i = 0; i < bLength; i++) {
            bNum[i] = Integer.valueOf(bNumString[i]);
        }
 
        int result[] = new int[aLength];
        dfs(0,result,aNum,bNum,aLength,visit);
        Collections.sort(countList);
        System.out.println(countMap.get(countList.get(countList.size()-1)));
    }
 
    private static void dfs(int currentPos, int[] result, int[] aNum, int[] bNum, int aLength, int[] visit) {
        if (currentPos == aLength) {
            countCountMap(result,bNum);
            return;
        }
        int i = 0;
        while (i < aLength) {
            if (i >= aLength) {
                break;
            }
            if (visit[i] == 0) {
                visit[i] = 1;
                result[currentPos] = aNum[i];
                dfs(currentPos + 1, result, aNum, bNum, aLength, visit);
                visit[i] = 0;
            }
            i++;
        }
    }
 
    private static void countCountMap(int[] result, int[] bNum) {
        int count = 0;
        for (int i = 0; i < result.length; i++) {
            if (result[i] > bNum[i]) {
                count++;
            }
        }
        if (countMap.containsKey(count)) {
            countMap.put(count, countMap.get(count) + 1);
        } else {
            countMap.put(count, 1);
        }
 
        if (!countList.contains(count)) {
            countList.add(count);
        }
    }
}

验证：