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

华为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年真题(基站维修工程师)

基站维修工程师&#xff08;200分&#xff09; 小王是一名基站维护工程师&#xff0c;负责某区域的基站维护。 某地方有n个基站(1<n<10)&#xff0c;已知各基站之间的距离s(0<s<500)&#xff0c;并且基站x到基站y的距离&#xff0c;与基站y到基站x的距离并不一定会…...

在MySQL中为啥引入批量键访问(Batch Key Access, BKA)

批量键访问&#xff08;Batch Key Access, BKA&#xff09; 是 MySQL 在某些情况下用于优化 JOIN 操作的一种技术&#xff0c;特别是在通过索引进行 JOIN 时&#xff0c;它能有效减少查询的随机 I/O。批量键访问优化通过将一批主键或索引键一次性发送给存储引擎来查找匹配的行&…...

912.排序数组(归并排序)

目录 题目解法初始数组1. 分解阶段2. 合并阶段结果 为什么要创建长整型ll mid l ((r - l) >> 1);其中的>>是什么意思 题目 给你一个整数数组 nums&#xff0c;请你将该数组升序排列。 你必须在 不使用任何内置函数 的情况下解决问题&#xff0c;时间复杂度为 O…...

使用 cmake 在 x86 系统中为 arm 系统交叉编译程序

原理&#xff1a; 在 x86 系统里使用交叉编译工具链&#xff08;arm 版 gcc/g&#xff09;编译程序&#xff0c;然后放在 arm 系统里运行。 arm 版本 使用 lscpu 查看 cpu 架构 版本说明armv732 bitarmv8/arrch6464 bit 安装交叉编译工具链 # 针对 armv7 sudo apt install…...

软考(网工)——网络规划设计

文章目录 &#x1f550;综合布线1️⃣结构化布线系统2️⃣综合布线六大子系统3️⃣综合布线物理结构图 &#x1f551;网络分析与设计1️⃣网络规划设计模型2️⃣网络流量分析3️⃣网络安全技术措施表4️⃣技术评价 &#x1f552;网络结构与功能1️⃣局域网结构类型2️⃣三层架构…...

即插即用特征融合模块,即用即涨点!

特征融合&#xff08;Feature Fusion&#xff09;是深度学习中的一种重要技术&#xff0c;它可以帮助模型更好地理解数据的内在结构和规律&#xff0c;提高模型的性能和泛化能力。 另外&#xff0c;特征融合还可以提高模型的分类准确率&#xff0c;减少过拟合风险&#xff0c;…...

蓝桥算法双周赛 第 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相同作者&#xff0c;最新文章会在网站更新&#xff0c;欢迎收藏书签 Cursor 智能代码补全详解(Tab) 概述 Cursor的智能代码补全&#xff0c;也就是快捷键Tab&#xff0c;是其最强大和独特的AI辅助编程工具之一。本教程将详细介绍…...

数据结构《顺序表》

文章目录 前言一、什么是顺序表&#xff1f;1.1 顺序表的概念1.2 顺序表的建立 二、MyArrayList的实现三、顺序表的方法四、关于顺序表的例子总结 前言 提示&#xff1a;这里涉及到的ArrayList类是一个泛型类&#xff0c;同时后面的很多内容都会涉及到泛型&#xff0c;如果不了…...

视频分享网站毕业设计基于SpringBootSSM框架

目录 1.摘要 2.引言 2.1 研究意义 3 功能描述 3.1‌功能图展示 ‌3.2非功能需求‌ 4. 需求分析 4.1前端技术 4.2后端技术 4.3视频处理技术 4.4内容分发网络&#xff08;CDN&#xff09; 4.5其他关键技术 计算机毕业设计/springboot/javaWEB/J2EE/MYSQL数据库/vue前后…...

Python多进程学习与使用:全面指南

Python多进程学习与使用&#xff1a;全面指南 目录 引言什么是多进程&#xff1f;为什么使用多进程&#xff1f;Python中的多进程模块&#xff1a;multiprocessing创建进程的基本方法进程间通信进程池多进程与多线程的比较常见问题和解决方案最佳实践和性能优化实战项目&…...

HTTP Proxy环境下部署Microsoft Entra Connect和Health Agents

在企业环境中&#xff0c;时常需要通过使用HTTP Proxy访问Internet&#xff0c;在使用HTTP Proxy访问Internet的环境中部署Microsoft Entra Connect和Microsoft Entra Connect Health Agents可能会遇到一些额外的配置步骤&#xff0c;以便这些服务能够正常连接到Internet。 一…...

基于单片机的 OLED 显示终端设计分析与研究

摘要: 我国的经济发展速度正在不断加快,经济体制也在经历着一系列的改革,工业发展也正是受到了它的影响,逐步发生变化。在这样的背景下,传统的 LCD 显示技术,逐渐被显示效果更好,功耗更低的 OLED 代替。本文主要介绍了基于单片机的 OLED 显示终端设计,该设计目前具有很…...

基于Multisim压力报警器电路设计(含仿真和报告)

【全套资料.zip】压力报警器电路设计Multisim仿真设计数字电子技术 文章目录 功能一、Multisim仿真源文件二、原理文档报告资料下载【Multisim仿真报告讲解视频.zip】 功能 压力报警器包括:压力检测、信号放大、声光报警当电路检测到系统压力正常时&#xff0c;不进行声、光报…...

基于Springboot的在线考试与学习交流平台的设计与实现

基于Springboot的在线考试与学习交流平台 开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 数据库&#xff1a;mysql 5.7 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;idea 源码获取&#xff1a;https://download.csdn.net/downlo…...

“避免序列化灾难:掌握实现 Serializable 的真相!(二)”

文章目录 一、什么是序列化&#xff1f;二、Serializable 是如何起作用的&#xff1f;三、为什么不自动序列化所有对象&#xff1f;四、Java 序列化的底层原理序列化的核心步骤&#xff1a; 五、反序列化的原理六、总结&#xff1a;为什么必须实现 Serializable 才能序列化&…...

中国工商银行智能运维体系建设

随着信息技术的快速发展,分布式架构已经成为主流的系统架构形式。基于分布式架构的系统具有资源利用率高、可扩展性好等优点,已广泛应用于各类企业信息系统之中。分布式监控系统应运而生,它通过在各个节点部署轻量级代理程序,实现对分布式系统的监控数据采集和分析,有效地解决…...

如何将logism电路转为verilog(一)

好长时间没写博客了 下文中提到的文件可在此仓库下载&#xff1a;https://github.com/deadfffool/HUST-Computer-Organization-Big-Homework/tree/main 在转换为verilog之前&#xff0c;需要对logisim电路做以下几点改动&#xff1a; 首先将下载的logisim_change.jar放在与log…...

【论文笔记】X-Former: Unifying Contrastive and Reconstruction Learning for MLLMs

&#x1f34e;个人主页&#xff1a;小嗷犬的个人主页 &#x1f34a;个人网站&#xff1a;小嗷犬的技术小站 &#x1f96d;个人信条&#xff1a;为天地立心&#xff0c;为生民立命&#xff0c;为往圣继绝学&#xff0c;为万世开太平。 基本信息 标题: 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…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

掌握 HTTP 请求:理解 cURL GET 语法

cURL 是一个强大的命令行工具&#xff0c;用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中&#xff0c;cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...

深入浅出Diffusion模型:从原理到实践的全方位教程

I. 引言&#xff1a;生成式AI的黎明 – Diffusion模型是什么&#xff1f; 近年来&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;领域取得了爆炸性的进展&#xff0c;模型能够根据简单的文本提示创作出逼真的图像、连贯的文本&#xff0c;乃至更多令人惊叹的…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...

【Veristand】Veristand环境安装教程-Linux RT / Windows

首先声明&#xff0c;此教程是针对Simulink编译模型并导入Veristand中编写的&#xff0c;同时需要注意的是老用户编译可能用的是Veristand Model Framework&#xff0c;那个是历史版本&#xff0c;且NI不会再维护&#xff0c;新版本编译支持为VeriStand Model Generation Suppo…...