华为OD机试：田忌赛马

题目描述

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

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

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

输入描述

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

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

输出描述

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

用例

题目解析

1.首先，将数组a和b按照从小到大的顺序进行排序。

2.然后，遍历数组a，对于每个元素a[i]，找到在数组b中第一个大于a[i]的元素b[j]，并将a[i]与b[j]交换位置。

3.重复步骤2，直到遍历完数组a。

4.统计所有可以达到最优结果的a数组的数量。

JS算法源码
const rl = require("readline").createInterface({ input: process.stdin });
const readline = async () => (await rl[Symbol.asyncIterator]().next()).value;

(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;
      }
    } else {
      for (let i = 0; i < a.length; i++) {
        if (!used[i]) {
          used[i] = true;
          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.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    static List<Integer> a = new ArrayList<>();
    static List<Integer> b = new ArrayList<>();

    static int maxBiggerCount = 0;
    static int ans = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        a = parseInput(br.readLine());
        b = parseInput(br.readLine());

        dfs(0, new HashSet<>(), 0);

        System.out.println(ans);
    }

    public static void dfs(int level, Set<Integer> used, int biggerCount) {
        if (level >= a.size()) {
            if (biggerCount > maxBiggerCount) {
                maxBiggerCount = biggerCount;
                ans = 1;
            } else if (biggerCount == maxBiggerCount) {
                ans++;
            }

            return;
        }

        for (int i = 0; i < a.size(); i++) {
            if (!used.add(i)) continue;

            dfs(level + 1, used, biggerCount + (a.get(i) > b.get(level) ? 1 : 0));
            used.remove(i);
        }
    }

    private static List<Integer> parseInput(String line) {
        List<Integer> list = new ArrayList<>();
        for (String part : line.split(" ")) {
            list.add(Integer.parseInt(part));
        }
        return list;
    }
}

Python算法源码
 
def dfs(level, biggerCount, maxBiggerCount, ans):
    if level >= len(a):
        if biggerCount > maxBiggerCount:
            return biggerCount, 1
        elif biggerCount == maxBiggerCount:
            return maxBiggerCount, ans + 1
        else:
            return maxBiggerCount, ans

    maxBiggerCount, ans = dfs(level + 1, biggerCount + (1 if a[level] > b[level] else 0), maxBiggerCount, ans)
    return dfs(level + 1, biggerCount, maxBiggerCount, ans)

a = list(map(int, input().split()))
b = list(map(int, input().split()))

maxBiggerCount, ans = dfs(0, 0, 0, 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;
        dfs(level + 1, used, biggerCount + (a[i] > b[level] ? 1 : 0));
        used[i] = 0;
    }
}

int main() {
    int num;
    while (scanf("%d", &num)) {
        a[a_size++] = num;
        if (getchar() != ' ') break;
    }

    while (scanf("%d", &num)) {
        b[b_size++] = num;
        if (getchar() != ' ') break;
    }

    int used[MAX_SIZE] = {0};

    // 求解a的全排列
    dfs(0, used, 0);

    printf("%d\n", ans);

    return 0;
}