华为OD机试2024年真题(基站维修工程师)
基站维修工程师(200分)
小王是一名基站维护工程师,负责某区域的基站维护。
某地方有n个基站(1<n<10),已知各基站之间的距离s(0<s<500),并且基站x到基站y的距离,与基站y到基站x的距离并不一定会相同。
小王从基站1出发,途径每个基站1次,然后返回基站1,需要请你为他选择一条距离最短的路线。
>>输入描述
站点数n和各站点之间的距离(均为整数)。如:
3 {站点数} 0 2 1 {站点1到各站点的路程) 1 0 2 (站点2到各站点的路程} 2 1 0 {站点3到各站点的路程}
>>输出描述
最短路程的数值
>>示例1
输入
3 0 2 1 1 0 2 2 1 0输出
3
思路:
目标是解决典型的旅行商问题(TSP, Travelling Salesman Problem),即在一个给定的城市网络中,找到一条从起点城市出发,经过每个城市一次并最终返回起点的路径,使得路径的总距离最短。算法使用了递归(深度优先搜索)结合状态标记来遍历所有可能的路径,并通过回溯法不断比较最短路径。
输入:给定一个 size x size 的二维数组 arr,其中 arr[i][j] 表示城市 i 到城市 j 的距离。
输出:求解从城市0出发,经过每个城市一次并返回的最短路径长度。
步骤:
数据输入:读取城市数 size 和城市之间的距离矩阵 arr。
递归函数 recur:递归尝试从一个城市访问未访问过的下一个城市,记录当前路径长度,并使用状态数组 st 标记某个城市是否已经访问过。
状态回溯:递归探索完某条路径后,返回上一步,尝试其他未访问过的城市,最终比较得到最短路径。
结果输出:输出所有路径中的最小总距离。
代码段如下:
package com.rich.huawei.od_test;import java.util.Scanner;/*** @description* @Title Test01* @Author tang rui qi* @Date 2024/10/14 5:17*/
public class Test03 {static int res; // 用于保存最短路径的总距离// 递归函数// u: 当前访问的第几个城市// pre: 上一个访问的城市编号// temRes: 当前路径的总距离// size: 城市的总数// arr: 城市之间的距离矩阵// st: 访问状态数组,标记某个城市是否被访问过static void recur(int u, int pre, int temRes, int size, int[][] arr, boolean[] st) {// 如果已经访问完所有城市并回到起点城市if (u == size - 1) {// 将当前路径的总距离与最小距离进行比较,更新最小距离res = Math.min(res, temRes + arr[pre][0]);return;}// 遍历每个城市,寻找下一个未访问过的城市for (int i = 1; i < size; ++i) {if (st[i]) { // 如果该城市已被访问,则跳过continue;}st[i] = true; // 标记该城市为已访问// 递归访问下一个城市,并累加当前路径的距离recur(u + 1, i, temRes + arr[pre][i], size, arr, st);st[i] = false; // 回溯时将该城市重置为未访问状态}}public static void main(String[] args) {Scanner cin = new Scanner(System.in);int size = cin.nextInt(); // 读取城市的总数res = 0x3f3f3f3f; // 初始化最短路径为一个很大的值int[][] arr = new int[size][size]; // 城市之间的距离矩阵boolean[] st = new boolean[size]; // 访问状态数组// 读取距离矩阵的值for (int x = 0; x < size; ++x)for (int y = 0; y < size; ++y) arr[x][y] = cin.nextInt();// 从城市0开始递归搜索recur(0, 0, 0, size, arr, st);// 输出最短路径的总距离System.out.println(res);}}
相关文章:
华为OD机试2024年真题(基站维修工程师)
基站维修工程师(200分) 小王是一名基站维护工程师,负责某区域的基站维护。 某地方有n个基站(1<n<10),已知各基站之间的距离s(0<s<500),并且基站x到基站y的距离,与基站y到基站x的距离并不一定会…...
在MySQL中为啥引入批量键访问(Batch Key Access, BKA)
批量键访问(Batch Key Access, BKA) 是 MySQL 在某些情况下用于优化 JOIN 操作的一种技术,特别是在通过索引进行 JOIN 时,它能有效减少查询的随机 I/O。批量键访问优化通过将一批主键或索引键一次性发送给存储引擎来查找匹配的行&…...
912.排序数组(归并排序)
目录 题目解法初始数组1. 分解阶段2. 合并阶段结果 为什么要创建长整型ll mid l ((r - l) >> 1);其中的>>是什么意思 题目 给你一个整数数组 nums,请你将该数组升序排列。 你必须在 不使用任何内置函数 的情况下解决问题,时间复杂度为 O…...
使用 cmake 在 x86 系统中为 arm 系统交叉编译程序
原理: 在 x86 系统里使用交叉编译工具链(arm 版 gcc/g)编译程序,然后放在 arm 系统里运行。 arm 版本 使用 lscpu 查看 cpu 架构 版本说明armv732 bitarmv8/arrch6464 bit 安装交叉编译工具链 # 针对 armv7 sudo apt install…...
软考(网工)——网络规划设计
文章目录 🕐综合布线1️⃣结构化布线系统2️⃣综合布线六大子系统3️⃣综合布线物理结构图 🕑网络分析与设计1️⃣网络规划设计模型2️⃣网络流量分析3️⃣网络安全技术措施表4️⃣技术评价 🕒网络结构与功能1️⃣局域网结构类型2️⃣三层架构…...
即插即用特征融合模块,即用即涨点!
特征融合(Feature Fusion)是深度学习中的一种重要技术,它可以帮助模型更好地理解数据的内在结构和规律,提高模型的性能和泛化能力。 另外,特征融合还可以提高模型的分类准确率,减少过拟合风险,…...
蓝桥算法双周赛 第 19 场 小白入门赛
打开石门 只要有相连的一样字母就可以消成一个 string s; int ans;void solve() {cin >> s;int len 0;for (int i 0;i < s.size();i ){if (s[i] L) len ;else //遇到Q{ans (len ? 1 : 0); //消除累计的Llen 0;ans ;//遇到Q}}//QLLLL时,最后遇不到Q让累计的L消…...
Cursor零基础小白教程系列「进阶」 - Cursor 智能代码补全详解(Tab)
最适合小白零基础的Cursor教程 网站lookai.top相同作者,最新文章会在网站更新,欢迎收藏书签 Cursor 智能代码补全详解(Tab) 概述 Cursor的智能代码补全,也就是快捷键Tab,是其最强大和独特的AI辅助编程工具之一。本教程将详细介绍…...
数据结构《顺序表》
文章目录 前言一、什么是顺序表?1.1 顺序表的概念1.2 顺序表的建立 二、MyArrayList的实现三、顺序表的方法四、关于顺序表的例子总结 前言 提示:这里涉及到的ArrayList类是一个泛型类,同时后面的很多内容都会涉及到泛型,如果不了…...
视频分享网站毕业设计基于SpringBootSSM框架
目录 1.摘要 2.引言 2.1 研究意义 3 功能描述 3.1功能图展示 3.2非功能需求 4. 需求分析 4.1前端技术 4.2后端技术 4.3视频处理技术 4.4内容分发网络(CDN) 4.5其他关键技术 计算机毕业设计/springboot/javaWEB/J2EE/MYSQL数据库/vue前后…...
Python多进程学习与使用:全面指南
Python多进程学习与使用:全面指南 目录 引言什么是多进程?为什么使用多进程?Python中的多进程模块:multiprocessing创建进程的基本方法进程间通信进程池多进程与多线程的比较常见问题和解决方案最佳实践和性能优化实战项目&…...
HTTP Proxy环境下部署Microsoft Entra Connect和Health Agents
在企业环境中,时常需要通过使用HTTP Proxy访问Internet,在使用HTTP Proxy访问Internet的环境中部署Microsoft Entra Connect和Microsoft Entra Connect Health Agents可能会遇到一些额外的配置步骤,以便这些服务能够正常连接到Internet。 一…...
基于单片机的 OLED 显示终端设计分析与研究
摘要: 我国的经济发展速度正在不断加快,经济体制也在经历着一系列的改革,工业发展也正是受到了它的影响,逐步发生变化。在这样的背景下,传统的 LCD 显示技术,逐渐被显示效果更好,功耗更低的 OLED 代替。本文主要介绍了基于单片机的 OLED 显示终端设计,该设计目前具有很…...
基于Multisim压力报警器电路设计(含仿真和报告)
【全套资料.zip】压力报警器电路设计Multisim仿真设计数字电子技术 文章目录 功能一、Multisim仿真源文件二、原理文档报告资料下载【Multisim仿真报告讲解视频.zip】 功能 压力报警器包括:压力检测、信号放大、声光报警当电路检测到系统压力正常时,不进行声、光报…...
基于Springboot的在线考试与学习交流平台的设计与实现
基于Springboot的在线考试与学习交流平台 开发语言:Java 框架:springboot JDK版本:JDK1.8 数据库:mysql 5.7 数据库工具:Navicat11 开发软件:idea 源码获取:https://download.csdn.net/downlo…...
“避免序列化灾难:掌握实现 Serializable 的真相!(二)”
文章目录 一、什么是序列化?二、Serializable 是如何起作用的?三、为什么不自动序列化所有对象?四、Java 序列化的底层原理序列化的核心步骤: 五、反序列化的原理六、总结:为什么必须实现 Serializable 才能序列化&…...
中国工商银行智能运维体系建设
随着信息技术的快速发展,分布式架构已经成为主流的系统架构形式。基于分布式架构的系统具有资源利用率高、可扩展性好等优点,已广泛应用于各类企业信息系统之中。分布式监控系统应运而生,它通过在各个节点部署轻量级代理程序,实现对分布式系统的监控数据采集和分析,有效地解决…...
如何将logism电路转为verilog(一)
好长时间没写博客了 下文中提到的文件可在此仓库下载:https://github.com/deadfffool/HUST-Computer-Organization-Big-Homework/tree/main 在转换为verilog之前,需要对logisim电路做以下几点改动: 首先将下载的logisim_change.jar放在与log…...
【论文笔记】X-Former: Unifying Contrastive and Reconstruction Learning for MLLMs
🍎个人主页:小嗷犬的个人主页 🍊个人网站:小嗷犬的技术小站 🥭个人信条:为天地立心,为生民立命,为往圣继绝学,为万世开太平。 基本信息 标题: X-Former: Unifying Contr…...
带权并查集注意事项
食物链 #include<bits/stdc.h> using namespace std; const int N5e410; int p[N],d[N]; int find(int x) {if(p[x]!x){int rootfind(p[x]);d[x]d[p[x]];p[x]root;}return p[x]; } int main() {int n,k;cin>>n>>k;for(int i1;i<n;i)p[i]i;int ans0;while…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...
Webpack性能优化:构建速度与体积优化策略
一、构建速度优化 1、升级Webpack和Node.js 优化效果:Webpack 4比Webpack 3构建时间降低60%-98%。原因: V8引擎优化(for of替代forEach、Map/Set替代Object)。默认使用更快的md4哈希算法。AST直接从Loa…...
Android写一个捕获全局异常的工具类
项目开发和实际运行过程中难免会遇到异常发生,系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler,它是Thread的子类(就是package java.lang;里线程的Thread)。本文将利用它将设备信息、报错信息以及错误的发生时间都…...
若依登录用户名和密码加密
/*** 获取公钥:前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...
土建施工员考试:建筑施工技术重点知识有哪些?
《管理实务》是土建施工员考试中侧重实操应用与管理能力的科目,核心考查施工组织、质量安全、进度成本等现场管理要点。以下是结合考试大纲与高频考点整理的重点内容,附学习方向和应试技巧: 一、施工组织与进度管理 核心目标: 规…...
