OJ-1014田忌赛马

示例1：

输入
11 8 20
10 13 7
输出
1

示例2：
输入
11 12 20
10 13 7
输出
2

示例3：
输入
1 2 3
4 5 6
输出
6

解题思路：

问题的关键在于调整数组a的顺序,使得尽可能多的a[i] > b[i]。为了达到最优结果,我们可以采用贪心的策略。具体思路如下:

1.首先，将数组a按照从大到小的顺序排序。
2.对于数组b,我们需要找到与每个b[i]相对应的最小的a[j],使得a[j]>b[i]。为了实现这一点,我们可以采用二分查找,找到a中第一个大于b[i]的数字的索引。
3.如果找到了对应的a[j],则将a[j]标记为已使用,并继续处理下一个b[i]。
4.如果没有找到对应的a[j],说明当前的b[i]无法找到满足条件的a[j],则尝试找下一个b[i+1]对应的a[j]。
5·重复以上步骤,直到处理完所有的b[i]。
最后,统计所有满足条件的a数组排列的数量即可。这样的贪心策略能够保证尽可能多的a[i]> b[i]。
在实际实现中，可以使用递归或迭代的方式来生成所有可能的a数组排列，然后根据上述贪心策略进行筛选。最终输出满足条件的a数组排列的数量。
 

优化：

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;public class 田忌赛马 {static Map<Integer, Integer> cnts = new HashMap<>();static int[] a;static int[] b;static int n;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);a = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();b = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();n = a.length;boolean[] st = new boolean[n];int[] nums = new int[n];dfs(0, st, nums);int maxcnt = 0;for (int k : cnts.keySet()) {if (k > maxcnt) {maxcnt = k;}}System.out.println(cnts.get(maxcnt));}private static void dfs(int u, boolean[] st, int[] nums) {if (u == n) {int cnt = 0;for (int i = 0; i < n; i++) {if (nums[i] > b[i]) {cnt += 1;}}cnts.put(cnt, cnts.getOrDefault(cnt, 0) + 1);return;}for (int i = 0; i < n; i++) {if (st[i]) continue;st[i] = true;nums[u] = a[i];dfs(u + 1, st, nums);st[i] = false;}}
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;public class 田忌赛马 {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);List<Integer> a = new ArrayList<>();List<Integer> b = new ArrayList<>();String[] s1 = scanner.nextLine().split(" ");String[] s2 = scanner.nextLine().split(" ");for (int i = 0; i < s1.length; i++) {a.add(Integer.parseInt(s1[i]));b.add(Integer.parseInt(s2[i]));}// 对列表a进行排序Collections.sort(a);int n = a.size();boolean[] st = new boolean[n];int[] nums = new int[n];Map<Integer, Integer> cnts = new HashMap<>();// 调用深度优先搜索函数dfs(0, a, b, st, nums, cnts);int maxcnt = 0, maxnum = cnts.getOrDefault(0, 0);// 寻找最大的相同数字数量和对应的排列情况数量for (Map.Entry<Integer, Integer> entry : cnts.entrySet()) {int k = entry.getKey();int v = entry.getValue();if (k > maxcnt) {maxcnt = k;maxnum = v;}}// 输出最大的相同数字数量System.out.println(maxnum);}// 定义深度优先搜索函数private static void dfs(int u, List<Integer> a, List<Integer> b, boolean[] st, int[] nums, Map<Integer, Integer> cnts) {// 如果已经遍历完所有数字，进行统计if (u == a.size()) {int cnt = 0;for (int i = 0; i < a.size(); i++) {if (nums[i] > b.get(i)) {cnt += 1;}}cnts.put(cnt, cnts.getOrDefault(cnt, 0) + 1);return;}// 遍历数字进行排列for (int i = 0; i < a.size(); i++) {// 如果当前数字已经被选择或者当前数字和前一个数字相同，做一个去重操作if (st[i] || (i > 0 && a.get(i).equals(a.get(i - 1)) && st[i - 1])) {continue;}st[i] = true;nums[u] = a.get(i);dfs(u + 1, a, b, st, nums, cnts);st[i] = false;}}
}

253.【华为OD机试】田忌赛马（贪心算法-Java&Python&C++&JS实现）_python 田忌赛马 华为od-CSDN博客