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

BD202311夏日漫步(最少步数,BFS或者 Dijstra)

本题链接:码蹄集

题目:

夏日夜晚,小度看着庭院中长长的走廊,萌发出想要在上面散步的欲望,小度注意到月光透过树荫落在地砖上,并且由于树荫的遮蔽度不通,所以月光的亮度不同,为了直观地看到每个格子的亮度,小度用了一些自然数来表示它们的亮度。亮度越高则数字越大,亮度相同的数字相同。

走廊是只有一行地砖的直走廊。上面一共有 nn 个格子,每个格子都被小度给予了一个数字 a_iai​ 来表示它的亮度。

小度现在站在 11 号格子,想要去到 nn 号格子。小度可以正向或反向移动到相邻的格子,每次需要花费 11 的体力。

同时小度还有瞬移的能力,其可以花费 11 的体力来瞬移到与当前格子亮度相同的格子上。而且由于小度视野有限,只能瞬移到在当前格子后的第一次亮度相同的格子上。这也意味着不能反向瞬移

小度想知道,到达 nn 号格子需要花费的最小体力是多少。以此制定一个最优秀的散步方案。

样例:

输入
6
0 1 2 3 1 5

输出
3

思路:

        根据题意,我们将小度移动方向,看成一块图,相邻格子之间作为路线,连接线,我们就可以很方便的,根据 BFS 或者 Dijkstra 来获取最少步数的操作了。

        注意!以后遇到最少步数,最少操作这些关键字,思路得要联想到 BFS 和 Dijkstra 这些最少操作数方面的算法啦!

Dijstra代码详解如下:

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define endl '\n'
#define x first
#define y second
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define INF 0x3f3f3f3f3f3f
#define umap unordered_map
#define uset unordered_set
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e5 + 10;
inline void solve();signed main()
{
//	freopen("a.txt", "r", stdin);IOS;int _t = 1;
//	cin >> _t;while (_t--){solve();}return 0;
}int n,ans;using PII = pair<int,int>;
umap<int,vector<int>>g,cnt; // g  记录连接线  cnt 记录可瞬移的点// Dijkstra 最短路求值
inline void Dijkstra()
{vector<int>dist(n + 1,INF);vector<bool>st(n + 1,false);dist[0] = 0;priority_queue<PII,vector<PII>,greater<PII>>q;q.emplace(PII(0,0));while(q.size()){PII now = q.top();q.pop();if(st[now.y])continue;st[now.y] = true;int a = now.y,dis = now.x;for(int i = 0;i < (int)g[a].size();++i){int j = g[a][i];if(dist[j] > dis + 1) dist[j] = dis + 1;q.emplace(PII(dist[j],j));}}ans = dist[n - 1];
}inline void solve()
{cin >> n;uset<int>node;	// 记录 所有点for(int i = 0,x;i < n;++i){cin >> x;node.emplace(x);cnt[x].emplace_back(i);	// 记录可瞬移的点if(i - 1 >= 0){// 小度可以正向或反向移动到相邻的格子g[i].emplace_back(i - 1);g[i - 1].emplace_back(i);}}for(auto &i:node){for(int j = 0;j + 1 < (int)cnt[i].size();++j){// 不能反向瞬移,只能瞬移到在当前格子后的第一次亮度相同的格子上// 所以我们只连接相邻可瞬移的g[cnt[i][j]].emplace_back(cnt[i][j + 1]);}}Dijkstra();cout << ans << endl;
}

最后提交:​​​​​​​​​​​​​​

BFS代码详解如下:

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define endl '\n'
#define x first
#define y second
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define INF 0x3f3f3f3f3f3f
#define umap unordered_map
#define uset unordered_set
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e5 + 10;
inline void solve();signed main()
{
//	freopen("a.txt", "r", stdin);IOS;int _t = 1;
//	cin >> _t;while (_t--){solve();}return 0;
}int n,ans;using PII = pair<int,int>;
umap<int,vector<int>>g,cnt; // g  记录连接线  cnt 记录可瞬移的点// BFS 求最短路
inline int BFS()
{vector<bool>st(N,false);queue<int>q;int step = 0;q.emplace(0);while(q.size()){int sz = q.size();while(sz--){int now = q.front();q.pop();st[now] = true;if(now == n - 1) return step;for(int i = 0;i < (int)g[now].size();++i){int j = g[now][i];if(!st[j]){st[j] = true;q.emplace(j);}}}++step;}return 0;
}inline void solve()
{cin >> n;uset<int>node;	// 记录 所有点for(int i = 0,x;i < n;++i){cin >> x;node.emplace(x);cnt[x].emplace_back(i);	// 记录可瞬移的点if(i - 1 >= 0){// 小度可以正向或反向移动到相邻的格子g[i].emplace_back(i - 1);g[i - 1].emplace_back(i);}}for(auto &i:node){for(int j = 0;j + 1 < (int)cnt[i].size();++j){// 不能反向瞬移,只能瞬移到在当前格子后的第一次亮度相同的格子上// 所以我们只连接相邻可瞬移的g[cnt[i][j]].emplace_back(cnt[i][j + 1]);}}int ans = BFS();cout << ans << endl;
}

最后提交:

相关文章:

BD202311夏日漫步(最少步数,BFS或者 Dijstra)

本题链接&#xff1a;码蹄集 题目&#xff1a; 夏日夜晚&#xff0c;小度看着庭院中长长的走廊&#xff0c;萌发出想要在上面散步的欲望&#xff0c;小度注意到月光透过树荫落在地砖上&#xff0c;并且由于树荫的遮蔽度不通&#xff0c;所以月光的亮度不同&#xff0c;为了直…...

React - 你知道props和state之间深层次的区别吗

难度级别:初级及以上 提问概率:60% 如果把React组件看做一个函数的话,props更像是外部传入的参数,而state更像是函数内部定义的变量。那么他们还有哪些更深层次的区别呢,我们来看一下。 首先说props,他是组件外部传入的参数,我们知道…...

mysql 查询实战-变量方式-解答

对mysql 查询实战-变量方式-题目&#xff0c;进行一个解答。&#xff08;先看题&#xff0c;先做&#xff0c;再看解答&#xff09; 1、查询表中⾄少连续三次的数字 1&#xff0c;处理思路 要计算连续出现的数字&#xff0c;加个前置变量&#xff0c;记录上一个的值&#xff0c…...

SpringBoot3配置SpringSecurity6

访问1&#xff1a;localhost:8080/security&#xff0c;返回&#xff1a;需要先认证才能访问&#xff08;说明没有权限&#xff09; 访问2&#xff1a;localhost:8080/anonymous&#xff0c;返回&#xff1a;anonymous&#xff08;说明正常访问&#xff09; 相关文件如下&…...

Unity之Unity面试题(三)

内容将会持续更新&#xff0c;有错误的地方欢迎指正&#xff0c;谢谢! Unity之Unity面试题&#xff08;三&#xff09; TechX 坚持将创新的科技带给世界&#xff01; 拥有更好的学习体验 —— 不断努力&#xff0c;不断进步&#xff0c;不断探索 TechX —— 心探索、心进取…...

Linux命令-dos2unix命令(将DOS格式文本文件转换成Unix格式)

说明 dos2unix命令 用来将DOS格式的文本文件转换成UNIX格式的&#xff08;DOS/MAC to UNIX text file format converter&#xff09;。DOS下的文本文件是以 \r\n 作为断行标志的&#xff0c;表示成十六进制就是0D0A。而Unix下的文本文件是以\n作为断行标志的&#xff0c;表示成…...

企业怎么做数据分析

数据分析在当今信息化时代扮演着至关重要的角色。能够准确地收集、分析和利用数据&#xff0c;对企业的决策和发展都具有重要意义。数聚将介绍企业如何合理地利用数据分析&#xff0c;如何协助企业在竞争激烈的市场中取得优势。 一、建立完善的数据收集系统 在进行数据分析之…...

1111111111

c语言中的小小白-CSDN博客c语言中的小小白关注算法,c,c语言,贪心算法,链表,mysql,动态规划,后端,线性回归,数据结构,排序算法领域.https://blog.csdn.net/bhbcdxb123?spm1001.2014.3001.5343 给大家分享一句我很喜欢我话&#xff1a; 知不足而奋进&#xff0c;望远山而前行&am…...

[面向对象] 单例模式与工厂模式

单例模式 是一种创建模式&#xff0c;保证一个类只有一个实例&#xff0c;且提供访问实例的全局节点。 工厂模式 面向对象其中的三大原则&#xff1a; 单一职责&#xff1a;一个类只有一个职责&#xff08;Game类负责什么时候创建英雄机&#xff0c;而不需要知道创建英雄机要…...

《前端防坑》- JS基础 - 你觉得typeof nullValue === null 么?

问题 JS原始类型有6种Undefined, Null, Number, String, Boolean, Symbol共6种。 在对原始类型使用typeof进行判断时, typeof stringValue string typeof numberValue number 如果一个变量(nullValue)的值为null&#xff0c;那么typeof nullValue "?" const u …...

【项目实战经验】DataKit迁移MySQL到openGauss(下)

上一篇我们分享了安装、设置、链接、启动等步骤&#xff0c;本篇我们将继续分享迁移、启动~ 目录 9. 离线迁移 9.1. 迁移插件安装 中断安装&#xff0c;比如 kill 掉java进程&#xff08;安装失败也要等待300s&#xff09; 下载安装包准备上传 缺少mysqlclient lib包 mysq…...

AI预测体彩排3第2弹【2024年4月13日预测--第1套算法开始计算第2次测试】

各位小伙伴&#xff0c;今天实在抱歉&#xff0c;周末回了趟老家&#xff0c;回来比较晚了&#xff0c;数据今天上午跑完后就回老家了&#xff0c;晚上8点多才回来&#xff0c;赶紧把预测结果发出来吧&#xff0c;虽然有点晚了&#xff0c;但是咱们前面说过了&#xff0c;目前的…...

【13137】质量管理(一)2024年4月串讲题组一

目录 1.选择题 2.多选题 3.简答题 4.论述题 5.计算题 6.论述题 【13137】质量管理-速 记 宝 典【全国通用】</...

Go语言中工作负载类型对并发的影响

在实际工作开发中我们需要根据工作负载是CPU密集型还是I/O密集型,使用不同的方式来解决问题。下面我们先来看这些概念,然后再讨论其影响。 在程序执行时,工作负载的执行时间会受以下因素限制: CPU的速度--例如,运行归并排序算法。工作负载被称为CPU密集型。I/O速度--例如…...

常用的Python内置函数

目录 1. getattr() 函数: 2. setattr() 函数: 3. id():返回对象的唯一标识符(内存地址)。 4. type():返回对象的类型。 5. isinstance(obj, classinfo):判断对象是否是某种类型或其子类的实例。 6. issubclass(class1, class2):判断一个类是否是另一个类的子类。 …...

MAC(M1芯片)编译Java项目慢且发热严重问题解决方案

目录 一、背景二、排查三、解决四、效果以及结果展示五、总结 一、背景 使用idea编译项目等操作&#xff0c;经常性发热严重&#xff0c;并且时间慢。直到昨天编译一个项目用时30分钟&#xff0c;电脑温度很高&#xff0c;并且有烧灼的味道&#xff0c;于是有了此篇文章。 二、…...

如何循环pandas格式的数据

如何循环pandas格式的数据 要循环处理 Pandas 格式的数据&#xff0c;可以使用 iterrows() 方法或者 iteritems() 方法。 iterrows() 方法&#xff1a; import pandas as pd# 假设 df 是你的 Pandas DataFrame for index, row in df.iterrows():# 在这里处理每一行的数据&am…...

新零售SaaS架构:客户管理系统架构设计(万字图文总结)

什么是客户管理系统&#xff1f; 客户管理系统&#xff0c;也称为CRM&#xff08;Customer Relationship Management&#xff09;&#xff0c;主要目标是建立、发展和维护好客户关系。 CRM系统围绕客户全生命周期的管理&#xff0c;吸引和留存客户&#xff0c;实现缩短销售周…...

Apache Spark

Apache Spark是一种开源的分布式计算系统&#xff0c;主要用于大数据处理和分析。Spark提供了一个高效的计算引擎&#xff0c;可以在分布式环境中处理大规模数据集。它支持多种编程语言&#xff0c;包括Scala、Java、Python和R。 Spark的核心概念是弹性分布式数据集&#xff0…...

CentOS7编译ZLMediaKit并使能WebRTC

使能WebRTC需要libsrtp库, libsrtp库需要openssl, 所以第一步先安装openssl, 系统自带的版本是1.0.2的, libsrtp需要1.1.1以上版本, 需要使用源码进行编译; GCC准备 需要安装gcc7以上版本, 并切换到gcc7的编译环境 yum install centos-release-scl yum install devtoolset-7…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...