当前位置: 首页 > news >正文

OJ-1014田忌赛马

示例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[i+1]对应的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 Map<Integer, 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);List<Integer> a = new ArrayList<>();List<Integer> 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];Map<Integer, Integer> cnts = new HashMap<>();// 调用深度优先搜索函数dfs(0, a, b, st, nums, cnts);int maxcnt = 0, maxnum = cnts.getOrDefault(0, 0);// 寻找最大的相同数字数量和对应的排列情况数量for (Map.Entry<Integer, 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, List<Integer> a, List<Integer> b, boolean[] st, int[] nums, Map<Integer, 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机试】田忌赛马(贪心算法-Java&Python&C++&JS实现)_python 田忌赛马 华为od-CSDN博客

http://www.lryc.cn/news/466232.html

相关文章:

  • Excel重新踩坑3:条件格式;基本公式运算符;公式中的单元格引用方式;公式菜单栏其他有用的功能说明;
  • 【AI知识点】FAISS如何提高检索效率?
  • 【Git】Gitlab进行merge request的时候,出现待合并分支合并了主分支的问题的解决
  • jetson nano ubuntu20.04安装ros-Noetic
  • 【数据结构与算法】走进数据结构的“时间胶囊”——栈
  • 伺服增量式和绝对式的本质区别?
  • 应对 .DevicData-X-XXXXXXXX 勒索病毒:防御与恢复策略
  • 【代码随想录——数组——二刷】
  • spring-boot(4)
  • 深度学习模型:原理、架构与应用
  • 玩客云Armbian安装Casaos
  • redis过期提醒
  • AnaTraf | 提升网络性能:深入解析网络关键指标监控、TCP重传与TCP握手时间
  • 黑盒测试和白盒测试的具体方法(附加实际应用中的技巧和注意事项)
  • 基于ssm的小区物业管理系统
  • 4本SCI/SSCI期刊更名,10月WOS更新!速看!
  • 麒麟v10系统安装docker镜像
  • 基于SSM大学校医院信息管理系统的设计
  • 【JS】如何识别一个变量是不是数组对象
  • 探索 Python 幽默之源:pyjokes 库全解析
  • 苦寻多时,终于找到!这款免费GIS工具助你轻松搞定地形切片
  • OpenResty性能分析:以HelloWorld服务器为例
  • pb生成文件和反射
  • .net framework 3.5sp1安装错误卡住不动怎么解决
  • 毕业设计—基于 Inception-ResNet模型的皮肤癌分类系统实现
  • 什么是优秀的单元测试?
  • 服务器安装Anaconda,Anaconda安装Pytorch
  • YOLO目标检测理论详解,YOLOv1理论知识讲解,超w字精读(学习YOLO框架必备),全网最详细教程
  • SpringBoot3.x和OCR构建车牌识别系统
  • conda 容器学习笔记之一 -- 基础环境配置