题目描述
给定两个只包含数字的数组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 < a.length; i++) { if (used[i]) continue; // 树层去重 if (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 < a.length; i++) { if (used[i]) continue; // 树层去重 if (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 = 0ans = 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 <stdio.h>#include <stdlib.h>#define MAX_SIZE 10int 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; // 树层去重 if (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 <bits/stdc++.h>using namespace std;#define MAX_SIZE 10vector<int> splitCin(char separator) { string s; getline(cin, s); stringstream ss(s); string token; vector<int> res; while (getline(ss, token, separator)) { res.emplace_back(stoi(token)); } return res;}vector<int> a;vector<int> 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 < a.size(); i++) { if (used[i]) continue; // 树层去重 if (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 << ans << endl; return 0;}