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

题目描述

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

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

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

输入描述

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

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

输出描述

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

用例

题目解析

本题数量级不大，可以考虑暴力破解。即求解a数组的所有全排列，然后将a数组的每个全排列和b数组逐个元素进行比较，统计每个全排列中a[i] > b[i]的个数biggerCount。我们保留最大的biggerCount 为 maxBiggerCount。

最终统计的是a[i] > b[i]的个数为maxBiggerCount的全排列的数量。

关于全排列的求解，可以参考：

本题不需要我们输出具体排列，因此不用定义path记录全排列。

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("%dn", ans);

    return 0;
}