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…...

【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...

华为OD机考-机房布局
import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...