免费创建网站平台有哪些,三合一网站,苏州公司网站开发,wordpress知识管理系统示例1#xff1a;
输入 11 8 20 10 13 7 输出 1 示例2#xff1a; 输入 11 12 20 10 13 7 输出 2
示例3#xff1a; 输入 1 2 3 4 5 6 输出 6
解题思路#xff1a;
问题的关键在于调整数组a的顺序,使得尽可能多的a[i] b[i]。为了达到最优结果,我们可以采用贪心的策…示例1
输入 11 8 20 10 13 7 输出 1 示例2 输入 11 12 20 10 13 7 输出 2
示例3 输入 1 2 3 4 5 6 输出 6
解题思路
问题的关键在于调整数组a的顺序,使得尽可能多的a[i] b[i]。为了达到最优结果,我们可以采用贪心的策略。具体思路如下:
1.首先将数组a按照从大到小的顺序排序。 2.对于数组b,我们需要找到与每个b[i]相对应的最小的a[j],使得a[j]b[i]。为了实现这一点,我们可以采用二分查找,找到a中第一个大于b[i]的数字的索引。 3.如果找到了对应的a[j],则将a[j]标记为已使用,并继续处理下一个b[i]。 4.如果没有找到对应的a[j],说明当前的b[i]无法找到满足条件的a[j],则尝试找下一个b[i1]对应的a[j]。 5·重复以上步骤,直到处理完所有的b[i]。 最后,统计所有满足条件的a数组排列的数量即可。这样的贪心策略能够保证尽可能多的a[i] b[i]。 在实际实现中可以使用递归或迭代的方式来生成所有可能的a数组排列然后根据上述贪心策略进行筛选。最终输出满足条件的a数组排列的数量。
优化
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;public class 田忌赛马 {static MapInteger, Integer cnts new HashMap();static int[] a;static int[] b;static int n;public static void main(String[] args) {Scanner scanner new Scanner(System.in);a Arrays.stream(scanner.nextLine().split( )).mapToInt(Integer::parseInt).toArray();b Arrays.stream(scanner.nextLine().split( )).mapToInt(Integer::parseInt).toArray();n a.length;boolean[] st new boolean[n];int[] nums new int[n];dfs(0, st, nums);int maxcnt 0;for (int k : cnts.keySet()) {if (k maxcnt) {maxcnt k;}}System.out.println(cnts.get(maxcnt));}private static void dfs(int u, boolean[] st, int[] nums) {if (u n) {int cnt 0;for (int i 0; i n; i) {if (nums[i] b[i]) {cnt 1;}}cnts.put(cnt, cnts.getOrDefault(cnt, 0) 1);return;}for (int i 0; i n; i) {if (st[i]) continue;st[i] true;nums[u] a[i];dfs(u 1, st, nums);st[i] false;}}
} import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;public class 田忌赛马 {public static void main(String[] args) {Scanner scanner new Scanner(System.in);ListInteger a new ArrayList();ListInteger b new ArrayList();String[] s1 scanner.nextLine().split( );String[] s2 scanner.nextLine().split( );for (int i 0; i s1.length; i) {a.add(Integer.parseInt(s1[i]));b.add(Integer.parseInt(s2[i]));}// 对列表a进行排序Collections.sort(a);int n a.size();boolean[] st new boolean[n];int[] nums new int[n];MapInteger, Integer cnts new HashMap();// 调用深度优先搜索函数dfs(0, a, b, st, nums, cnts);int maxcnt 0, maxnum cnts.getOrDefault(0, 0);// 寻找最大的相同数字数量和对应的排列情况数量for (Map.EntryInteger, Integer entry : cnts.entrySet()) {int k entry.getKey();int v entry.getValue();if (k maxcnt) {maxcnt k;maxnum v;}}// 输出最大的相同数字数量System.out.println(maxnum);}// 定义深度优先搜索函数private static void dfs(int u, ListInteger a, ListInteger b, boolean[] st, int[] nums, MapInteger, Integer cnts) {// 如果已经遍历完所有数字进行统计if (u a.size()) {int cnt 0;for (int i 0; i a.size(); i) {if (nums[i] b.get(i)) {cnt 1;}}cnts.put(cnt, cnts.getOrDefault(cnt, 0) 1);return;}// 遍历数字进行排列for (int i 0; i a.size(); i) {// 如果当前数字已经被选择或者当前数字和前一个数字相同做一个去重操作if (st[i] || (i 0 a.get(i).equals(a.get(i - 1)) st[i - 1])) {continue;}st[i] true;nums[u] a.get(i);dfs(u 1, a, b, st, nums, cnts);st[i] false;}}
} 253.【华为OD机试】田忌赛马贪心算法-JavaPythonCJS实现_python 田忌赛马 华为od-CSDN博客
