(200分)- 田忌赛马（Java JS Python C）

(200分)- 田忌赛马Java JS Python C题目描述给定两个只包含数字的数组ab调整数组 a 里面的数字的顺序使得尽可能多的a[i] b[i]。数组a和b中的数字各不相同。输出所有可以达到最优结果的a数组的结果。输入描述输入的第一行是数组 a 中的数字其中只包含数字每两个数字之间相隔一个空格a数组大小不超过10。输入的第二行是数组 b 中的数字其中只包含数字每两个数字之间相隔一个空格b数组大小不超过10。输出描述输出所有可以达到最优结果的 a 数组的数量。用例输入11 8 2010 13 7输出1说明最优结果只有一个a [11, 20, 8]故输出1输入11 12 2010 13 7输出2说明有两个a数组的排列可以达到最优结果[12, 20, 11] 和 [11, 20, 12]故输出2输入1 2 34 5 6输出6说明a无论如何都会全输故a任意排列都行输出所有a数组的排列6种排法。题目解析由于题目数据规模较小可以采用暴力解法。具体思路如下枚举数组a的所有可能排列组合对于每个排列逐元素与数组b进行比较统计满足a[i] b[i]的元素个数biggerCount记录所有排列中最大的biggerCount值maxBiggerCount最终统计满足biggerCount等于maxBiggerCount的排列数量关于排列生成 由于只需统计数量而不需要具体排列可以省略存储中间排列结果的步骤直接进行计数即可。JS算法源码const rl require(readline).createInterface({ input: process.stdin }); var iter rl[Symbol.asyncIterator](); const readline async () (await iter.next()).value; void (async function () { const a (await readline()).split( ).map(Number); const b (await readline()).split( ).map(Number); let maxBiggerCount 0; let ans 0; function dfs(level, used, biggerCount) { if (level a.length) { if (biggerCount maxBiggerCount) { maxBiggerCount biggerCount; ans 1; } else if (biggerCount maxBiggerCount) { ans 1; } } for (let i 0; i a.length; i) { if (used[i]) continue; used[i] true; // biggerCount记录当前全排列中a[level] b[level]的位置的数量, 此时a[level] a[i] dfs(level 1, used, biggerCount (a[i] b[level] ? 1 : 0)); used[i] false; } } dfs(0, new Array(a.length).fill(false), 0); console.log(ans); })();Java算法源码import java.util.Arrays; import java.util.Scanner; public class Main { static int[] a; static int[] b; static int maxBiggerCount 0; static int ans 0; public static void main(String[] args) { Scanner sc new Scanner(System.in); a Arrays.stream(sc.nextLine().split( )).mapToInt(Integer::parseInt).toArray(); b Arrays.stream(sc.nextLine().split( )).mapToInt(Integer::parseInt).toArray(); // 求解a的全排列 dfs(0, new boolean[a.length], 0); System.out.println(ans); } public static void dfs(int level, boolean[] used, int biggerCount) { if (level a.length) { if (biggerCount maxBiggerCount) { maxBiggerCount biggerCount; ans 1; } else if (biggerCount maxBiggerCount) { ans; } return; } for (int i 0; i a.length; i) { if (used[i]) continue; used[i] true; // biggerCount记录当前全排列中a[level] b[level]的位置的数量, 此时a[level] a[i] dfs(level 1, used, biggerCount (a[i] b[level] ? 1 : 0)); used[i] false; } } }Python算法源码# 输入获取 a list(map(int, input().split())) b list(map(int, input().split())) maxBiggerCount 0 ans 0 # 算法入口 def dfs(level, used, biggerCount): global maxBiggerCount, ans if level len(a): if biggerCount maxBiggerCount: maxBiggerCount biggerCount ans 1 elif biggerCount maxBiggerCount: ans 1 return for i in range(len(a)): if used[i]: continue used[i] True # biggerCount记录当前全排列中a[level] b[level]的位置的数量, 此时a[level] a[i] dfs(level 1, used, biggerCount (1 if a[i] b[level] else 0)) used[i] False # 算法调用 dfs(0, [False] * len(a), 0) print(ans)C算法源码#include stdio.h #define MAX_SIZE 10 int a[MAX_SIZE]; int a_size 0; int b[MAX_SIZE]; int b_size 0; int maxBiggerCount 0; int ans 0; void dfs(int level, int used[], int biggerCount) { if (level a_size) { if (biggerCount maxBiggerCount) { maxBiggerCount biggerCount; ans 1; } else if (biggerCount maxBiggerCount) { ans 1; } return; } for (int i 0; i a_size; i) { if (used[i]) continue; used[i] 1; // biggerCount记录当前全排列中a[level] b[level]的位置的数量, 此时a[level] a[i] dfs(level 1, used, biggerCount (a[i] b[level] ? 1 : 0)); used[i] 0; } } int main() { while (scanf(%d, a[a_size])) { if (getchar() ! ) break; } while (scanf(%d, b[b_size])) { if (getchar() ! ) break; } int used[MAX_SIZE] {0}; // 求解a的全排列 dfs(0, used, 0); printf(%d\n, ans); return 0; }