华为OD机试 - 田忌赛马（Java & JS & Python & C & 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种排法。

题目解析

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

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

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

LeetCode - 46 全排列_全排列 46 力扣-CSDN博客

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

---

2024.02.18

本题题目描述中说：

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

一开始我是理解为a中的各个数字互不相同，b中的各个数字互不相同。因此a的所有全排列是不存在重复情况的。

但是实际机考时，似乎a中是存在重复元素的。

而a中存在重复元素，意味着a的所有全排列也是存在重复情况的，因此我们应该要求解a的去重全排列。

关于去重全排列求解请看：

LeetCode - 47 全排列 II_leetcode 全排列2-CSDN博客

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  0 && a[i] == a[i - 1] && !used[i - 1]) 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;
    }
  }
  a.sort((a, b) => a - b);
  // 求解a的去重全排列
  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();
        Arrays.sort(a);
        // 求解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  0 && a[i] == a[i - 1] && !used[i - 1]) 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
        # 树层去重
        if i > 0 and a[i] == a[i - 1] and not used[i - 1]:
            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
# 求解a的去重全排列
a.sort()
dfs(0, [False] * len(a), 0)
print(ans)

C算法源码

#include 
#include 
#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  0 && a[i] == a[i - 1] && !used[i - 1]) 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 cmp(const void *a, const void *b) {
    return *((int *) a) - *((int *) b);
}
int main() {
    while (scanf("%d", &a[a_size++])) {
        if (getchar() != ' ') break;
    }
    while (scanf("%d", &b[b_size++])) {
        if (getchar() != ' ') break;
    }
    // 求解a的去重全排列
    qsort(a, a_size, sizeof(a[0]), cmp);
    int used[MAX_SIZE] = {0};
    dfs(0, used, 0);
    printf("%d\n", ans);
    return 0;
}

C++算法源码

#include 
using namespace std;
#define MAX_SIZE 10
vector splitCin(char separator) {
    string s;
    getline(cin, s);
    stringstream ss(s);
    string token;
    vector res;
    while (getline(ss, token, separator)) {
        res.emplace_back(stoi(token));
    }
    return res;
}
vector a;
vector b;
int maxBiggerCount = 0;
int ans = 0;
void dfs(int level, bool 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  0 && a[i] == a[i - 1] && !used[i - 1]) 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;
    }
}
int main() {
    a = splitCin(' ');
    b = splitCin(' ');
    // 求解a的去重全排列
    sort(a.begin(), a.end());
    bool used[MAX_SIZE] = {false};
    dfs(0, used, 0);
    cout