BD202311夏日漫步(最少步数,BFS或者 Dijstra)
本题链接:码蹄集
题目:
夏日夜晚,小度看着庭院中长长的走廊,萌发出想要在上面散步的欲望,小度注意到月光透过树荫落在地砖上,并且由于树荫的遮蔽度不通,所以月光的亮度不同,为了直观地看到每个格子的亮度,小度用了一些自然数来表示它们的亮度。亮度越高则数字越大,亮度相同的数字相同。
走廊是只有一行地砖的直走廊。上面一共有 nn 个格子,每个格子都被小度给予了一个数字 a_iai 来表示它的亮度。
小度现在站在 11 号格子,想要去到 nn 号格子。小度可以正向或反向移动到相邻的格子,每次需要花费 11 的体力。
同时小度还有瞬移的能力,其可以花费 11 的体力来瞬移到与当前格子亮度相同的格子上。而且由于小度视野有限,只能瞬移到在当前格子后的第一次亮度相同的格子上。这也意味着不能反向瞬移。
小度想知道,到达 nn 号格子需要花费的最小体力是多少。以此制定一个最优秀的散步方案。
样例:
|
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)
本题链接:码蹄集 题目: 夏日夜晚,小度看着庭院中长长的走廊,萌发出想要在上面散步的欲望,小度注意到月光透过树荫落在地砖上,并且由于树荫的遮蔽度不通,所以月光的亮度不同,为了直…...

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

mysql 查询实战-变量方式-解答
对mysql 查询实战-变量方式-题目,进行一个解答。(先看题,先做,再看解答) 1、查询表中⾄少连续三次的数字 1,处理思路 要计算连续出现的数字,加个前置变量,记录上一个的值,…...
SpringBoot3配置SpringSecurity6
访问1:localhost:8080/security,返回:需要先认证才能访问(说明没有权限) 访问2:localhost:8080/anonymous,返回:anonymous(说明正常访问) 相关文件如下&…...

Unity之Unity面试题(三)
内容将会持续更新,有错误的地方欢迎指正,谢谢! Unity之Unity面试题(三) TechX 坚持将创新的科技带给世界! 拥有更好的学习体验 —— 不断努力,不断进步,不断探索 TechX —— 心探索、心进取…...
Linux命令-dos2unix命令(将DOS格式文本文件转换成Unix格式)
说明 dos2unix命令 用来将DOS格式的文本文件转换成UNIX格式的(DOS/MAC to UNIX text file format converter)。DOS下的文本文件是以 \r\n 作为断行标志的,表示成十六进制就是0D0A。而Unix下的文本文件是以\n作为断行标志的,表示成…...
企业怎么做数据分析
数据分析在当今信息化时代扮演着至关重要的角色。能够准确地收集、分析和利用数据,对企业的决策和发展都具有重要意义。数聚将介绍企业如何合理地利用数据分析,如何协助企业在竞争激烈的市场中取得优势。 一、建立完善的数据收集系统 在进行数据分析之…...

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

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

《前端防坑》- JS基础 - 你觉得typeof nullValue === null 么?
问题 JS原始类型有6种Undefined, Null, Number, String, Boolean, Symbol共6种。 在对原始类型使用typeof进行判断时, typeof stringValue string typeof numberValue number 如果一个变量(nullValue)的值为null,那么typeof nullValue "?" const u …...

【项目实战经验】DataKit迁移MySQL到openGauss(下)
上一篇我们分享了安装、设置、链接、启动等步骤,本篇我们将继续分享迁移、启动~ 目录 9. 离线迁移 9.1. 迁移插件安装 中断安装,比如 kill 掉java进程(安装失败也要等待300s) 下载安装包准备上传 缺少mysqlclient lib包 mysq…...

AI预测体彩排3第2弹【2024年4月13日预测--第1套算法开始计算第2次测试】
各位小伙伴,今天实在抱歉,周末回了趟老家,回来比较晚了,数据今天上午跑完后就回老家了,晚上8点多才回来,赶紧把预测结果发出来吧,虽然有点晚了,但是咱们前面说过了,目前的…...
【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编译项目等操作,经常性发热严重,并且时间慢。直到昨天编译一个项目用时30分钟,电脑温度很高,并且有烧灼的味道,于是有了此篇文章。 二、…...
如何循环pandas格式的数据
如何循环pandas格式的数据 要循环处理 Pandas 格式的数据,可以使用 iterrows() 方法或者 iteritems() 方法。 iterrows() 方法: import pandas as pd# 假设 df 是你的 Pandas DataFrame for index, row in df.iterrows():# 在这里处理每一行的数据&am…...

新零售SaaS架构:客户管理系统架构设计(万字图文总结)
什么是客户管理系统? 客户管理系统,也称为CRM(Customer Relationship Management),主要目标是建立、发展和维护好客户关系。 CRM系统围绕客户全生命周期的管理,吸引和留存客户,实现缩短销售周…...
Apache Spark
Apache Spark是一种开源的分布式计算系统,主要用于大数据处理和分析。Spark提供了一个高效的计算引擎,可以在分布式环境中处理大规模数据集。它支持多种编程语言,包括Scala、Java、Python和R。 Spark的核心概念是弹性分布式数据集࿰…...
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 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

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

MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能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出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

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

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

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

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