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

题目描述

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

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

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

输入描述

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

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

输出描述

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

用例

输入	11 8 20 10 13 7
输出	1
说明	最优结果只有一个，a = [11, 20, 8]，故输出1

输入	11 12 20 10 13 7
输出	2
说明	有两个a数组的排列可以达到最优结果，[12, 20, 11] 和 [11, 20, 12]，故输出2

输入	1 2 3 4 5 6
输出	6
说明	a无论如何都会全输，故a任意排列都行，输出所有a数组的排列，6种排法。

题目解析

由于题目数据规模较小，可以采用暴力解法。具体思路如下：

1. 枚举数组a的所有可能排列组合
2. 对于每个排列，逐元素与数组b进行比较
3. 统计满足a[i] > b[i]的元素个数biggerCount
4. 记录所有排列中最大的biggerCount值maxBiggerCount
5. 最终统计满足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;
}