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博客
相关文章:
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]。为了达到最优结果,我们可以采用贪心的策…...
Excel重新踩坑3:条件格式;基本公式运算符;公式中的单元格引用方式;公式菜单栏其他有用的功能说明;
0、前言:以下内容是学习excel公式的基础内容。 1、需求:将表格特定区域中数值大小大于等于30,小于等于80的单元格,颜色填充为红色,大于80的,颜色填充为黄色。 新建规则之后也可以通过该功能清除规则。 2、基…...
【AI知识点】FAISS如何提高检索效率?
【AI论文解读】【AI知识点】【AI小项目】【AI战略思考】 FAISS(Facebook AI Similarity Search) 是一个高效的相似度搜索库,专门设计用于处理大规模的向量检索任务,尤其是在稠密向量的检索中表现出色。FAISS 能够显著提高检索效率…...
【Git】Gitlab进行merge request的时候,出现待合并分支合并了主分支的问题的解决
最近在公司开始用merge request进行代码合并了。 然后不知道为啥,如果待合并分支(A)进行merge request到主分支(B)的时候,如果A和B有冲突,然后我在gitlab上使用页面进行冲突的解决,比…...
jetson nano ubuntu20.04安装ros-Noetic
jetson nano ubuntu20.04 安装ros-Noetic 一. 初始准备nano连接wifinano网络配置二. 查看系统版本三. 开始安装1. 移除不需要的 amd64 架构2. 配置软件源3.安装 ROS Melodic`4. 解决 rosdep update报错`一. 初始准备 nano连接wifi nano网络配置 二. 查看系统版本 lsb_relea…...
【数据结构与算法】走进数据结构的“时间胶囊”——栈
大家好,我是小卡皮巴拉 文章目录 目录 引言 一.栈的基本概念 1.1 定义 1.2 特性 1.3 基本操作 二.栈的实现方式 2.1 顺序栈 2.2 链栈 三.顺序栈的实现 定义顺序栈的结构 初始化 入栈 检查栈是否为空 出栈 销毁 四.链栈的实现 定义链栈的结构 初始…...
伺服增量式和绝对式的本质区别?
伺服增量式和绝对式的本质区别? 增量式编码器是将位移转换成周期性的电信号,再把这个电信号转变成计数脉冲,用脉冲的个数表示位移的大小。以转动时输出脉冲,通过计数设备来知道其位置,当编码器不动或停电时,…...
应对 .DevicData-X-XXXXXXXX 勒索病毒:防御与恢复策略
引言 随着信息技术的快速发展,网络安全问题愈发严峻。勒索病毒作为一种恶性网络攻击手段,已成为企业和个人面临的重大威胁之一。尤其是 .DevicData-X-XXXXXXXX 勒索病毒,其通过加密用户数据并勒索赎金,给受害者带来了巨大的经济损…...
【代码随想录——数组——二刷】
数组 1. 二分查找(704) 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 1.1 二分法的第一种写法 我们定义 target 是在…...
spring-boot(4)
1.VueRouter安装与使用 2.状态管理VueX 3. 4. 5. 6....
深度学习模型:原理、架构与应用
深度学习(Deep Learning)是机器学习中的一个分支,基于人工神经网络的发展,尤其是多层神经网络的研究,使其在语音识别、图像处理、自然语言处理等领域取得了显著进展。深度学习的核心是通过大量数据的训练,学习到数据的内在结构和模式,并且具备自动从复杂的输入中提取特征…...
玩客云Armbian安装Casaos
#armbian安装docker apt install docker.io #armbian判断docker是否正常运行 systemctl status docker #查看版本 docker version #安装casaos方式一 wget -qO- https://get.casaos.io | bash #安装casaos方式二 curl -fsSL https://get.casaos.io | bash...
redis过期提醒
文章目录 redis过期提醒 redis过期提醒 有一次看redis的配置文件发现一个notify-keyspace-events配置,注释里边长篇大论的,那我得看看这是干啥的,看完注释内容,发现不得了了,redis竟然还有过期提醒的功能 接下来得大…...
AnaTraf | 提升网络性能:深入解析网络关键指标监控、TCP重传与TCP握手时间
AnaTraf 网络性能监控系统NPM | 全流量回溯分析 | 网络故障排除工具 在当今的数字化时代,网络的稳定性和性能对企业的运营效率至关重要。无论是内部通信、应用程序的运行,还是对外提供服务,网络都发挥着关键作用。对于网络工程师或IT运维人员…...
黑盒测试和白盒测试的具体方法(附加实际应用中的技巧和注意事项)
黑盒测试的具体方法 黑盒测试有多种具体的方法,以下是几种常见的黑盒测试技术: 等价类划分 定义:将输入数据划分为若干等价类,每个等价类中的数据被认为是等效的。目的:减少测试用例数量,同时覆盖所有可…...
基于ssm的小区物业管理系统
文未可获取一份本项目的java源码和数据库参考。 题目简介: 我国物权法的颁布以及经济的快速发展进一步提升了社区居民对物业服务和物业管理的要求,特别是对于社区安全、社区停车以及社区维修等各个方面提出了更为严格的要求。在这种背景下社区物业必须…...
4本SCI/SSCI期刊更名,10月WOS更新!速看!
期刊动态 2024年10月科睿唯安期刊目录更新 2024年10月22日,科睿唯安更新了WOS期刊目录,此次更新,期刊被编辑除名11本,停止出版1本,4本更名,停产1本,新增63本。 剔除期刊 11本期刊被剔 Enginee…...
麒麟v10系统安装docker镜像
最近把系统搞崩了,又重新安装了一个麒麟系统,yum更新发现不能安装docker,所以这里给出一个安装教程,分享出来,让大家少走弯路: # 配置阿里云 Centos8 镜像源,需要额外的一些依赖,而…...
基于SSM大学校医院信息管理系统的设计
管理员账户功能包括:系统首页,个人中心,校医管理,用户管理,在线问诊管理,线上挂号管理,病例记录管理,系统管理 校医账号功能包括:系统首页,个人中心…...
【JS】如何识别一个变量是不是数组对象
文章目录 1. Array.isArray()语法示例 2. Object.prototype.toString.call()语法示例 3. instanceof 操作符语法示例 4. 检查 constructor属性语法示例 总结 在 JavaScript 中,有几种方法可以用来识别一个变量是否是数组对象。以下是一些常用的方法: 1. …...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
