当前位置: 首页 > 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…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

前端中slice和splic的区别

1. slice slice 用于从数组中提取一部分元素&#xff0c;返回一个新的数组。 特点&#xff1a; 不修改原数组&#xff1a;slice 不会改变原数组&#xff0c;而是返回一个新的数组。提取数组的部分&#xff1a;slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...

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

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...