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

Leetcode.2477 到达首都的最少油耗

题目链接

Leetcode.2477 到达首都的最少油耗 rating : 2012

题目描述

给你一棵 n n n 个节点的树(一个无向、连通、无环图),每个节点表示一个城市,编号从 0 0 0 n − 1 n - 1 n1 ,且恰好有 n − 1 n - 1 n1 条路。 0 0 0 是首都。给你一个二维整数数组 r o a d s roads roads ,其中 r o a d s [ i ] = [ a i , b i ] roads[i] = [a_i, b_i] roads[i]=[ai,bi] ,表示城市 a i a_i ai b i b_i bi 之间有一条 双向路

每个城市里有一个代表,他们都要去首都参加一个会议。

每座城市里有一辆车。给你一个整数 s e a t s seats seats 表示每辆车里面座位的数目。

城市里的代表可以选择乘坐所在城市的车,或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。

请你返回到达首都最少需要多少升汽油。

示例 1:

在这里插入图片描述

输入:roads = [[0,1],[0,2],[0,3]], seats = 5
输出:3
解释:

  • 代表 1 直接到达首都,消耗 1 升汽油。
  • 代表 2 直接到达首都,消耗 1 升汽油。
  • 代表 3 直接到达首都,消耗 1 升汽油。 最少消耗 3 升汽油。
示例 2:

在这里插入图片描述

输入:roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 2
输出:7
解释:

  • 代表 2 到达城市 3 ,消耗 1 升汽油。
  • 代表 2 和代表 3 一起到达城市 1 ,消耗 1 升汽油。
  • 代表 2 和代表 3 一起到达首都,消耗 1 升汽油。
  • 代表 1 直接到达首都,消耗 1 升汽油。
  • 代表 5 直接到达首都,消耗 1 升汽油。
  • 代表 6 到达城市 4 ,消耗 1 升汽油。
  • 代表 4 和代表 6 一起到达首都,消耗 1 升汽油。 最少消耗 7 升汽油。
示例 3:

在这里插入图片描述

输入:roads = [], seats = 1
输出:0
解释:没有代表需要从别的城市到达首都。

提示:
  • 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1n105
  • r o a d s . l e n g t h = n − 1 roads.length = n - 1 roads.length=n1
  • r o a d s [ i ] . l e n g t h = 2 roads[i].length = 2 roads[i].length=2
  • 0 ≤ a i , b i < n 0 \leq a_i, b_i < n 0ai,bi<n
  • a i ≠ b i a_i \neq b_i ai=bi
  • r o a d s roads roads 表示一棵合法的树。
  • 1 ≤ s e a t s ≤ 1 0 5 1 \leq seats \leq 10^5 1seats105

解法:dfs + 贪心

越靠近起点 0 0 0 的边,经过的车越多,所消耗的燃料也就越多。

由于我们求得是消耗的最少的燃料,假设以点 v v v 为根节点的子树上的所有节点都要经过边 { u , v } \{ u,v\} {u,v} 到点 u u u,子树 v v v 的节点总数为 c n t v cnt_v cntv,那么要让 c n t v cnt_v cntv 个节点都被移动到 点 u u u ,最少需要 ⌈ c n t v s e a t s ⌉ \lceil \frac{cnt_v}{seats} \rceil seatscntv 辆车,为了用尽可能少的燃料,所以我们直接用 ⌈ c n t v s e a t s ⌉ \lceil \frac{cnt_v}{seats} \rceil seatscntv 辆车。

那么对于 边 { u , v } \{ u,v\} {u,v},一共有 ⌈ c n t v s e a t s ⌉ \lceil \frac{cnt_v}{seats} \rceil seatscntv 辆车通过了这条边,所以一共要消耗 ⌈ c n t v s e a t s ⌉ \lceil \frac{cnt_v}{seats} \rceil seatscntv 升燃料。

我们直接从 起点 0 0 0 开始遍历所有的边,记录总的燃料即可。

时间复杂度 : O ( n ) O(n) O(n)

C++代码:

using LL = long long;class Solution {
public:long long minimumFuelCost(vector<vector<int>>& roads, int seats) {unordered_map<int,vector<int>> g;int n = 0;for(auto &e:roads){int a = e[0] , b = e[1];n = max({a,b,n});g[a].push_back(b);g[b].push_back(a);}n++;//s[i] 就是以 i 为根节点的节点总数vector<int> s(n);LL ans = 0;function<int(int,int)> dfs = [&](int u,int fa) ->int{s[u] = 1;for(auto v:g[u]){if(v == fa) continue;s[u] += dfs(v,u);}//不统计根节点if(u != 0) ans += (s[u] + seats - 1) / seats;return s[u];};dfs(0,-1);return ans;}
};

相关文章:

Leetcode.2477 到达首都的最少油耗

题目链接 Leetcode.2477 到达首都的最少油耗 rating : 2012 题目描述 给你一棵 n n n 个节点的树&#xff08;一个无向、连通、无环图&#xff09;&#xff0c;每个节点表示一个城市&#xff0c;编号从 0 0 0 到 n − 1 n - 1 n−1 &#xff0c;且恰好有 n − 1 n - 1 n−…...

sizeof()、strlen()、length()、size()的区别(笔记)

​ 上面的笔记有点简陋&#xff0c;可以看一下下面这个博主的&#xff1a; c/c中sizeof()、strlen()、length()、size()详解和区别_csize,sizeof,length_xuechanba的博客-CSDN博客...

Redis击穿(热点key失效)

Redis击穿是指在高并发情况下&#xff0c;一个键在缓存中过期失效时&#xff0c;同时有大量请求访问该键&#xff0c;导致所有请求都落到数据库上&#xff0c;对数据库造成压力。这种情况下&#xff0c;数据库可能无法及时处理这些请求&#xff0c;导致性能下降甚至崩溃。 为了…...

分类预测 | Matlab实现OOA-CNN-SVM鱼鹰算法优化卷积支持向量机分类预测

分类预测 | Matlab实现OOA-CNN-SVM鱼鹰算法优化卷积支持向量机分类预测 目录 分类预测 | Matlab实现OOA-CNN-SVM鱼鹰算法优化卷积支持向量机分类预测分类效果基本描述程序设计参考资料 分类效果 基本描述 1.Matlab实现OOA-CNN-SVM鱼鹰算法优化卷积支持向量机分类预测&#xff0…...

class文件结构

文章目录 1. 常量池集合2. 访问标志3. 字段表集合4. 方法表集合5. 属性表集合 成员变量&#xff08;非静态&#xff09;的赋值过程&#xff1a;1. 默认初始化 2. 显示初始化/代码块中初始化 3. 构造器中初始化 4. 有了对象后对象。属性或者对象。方法的方式对成员变量进行赋值 …...

多重背包问题 一句话说清楚“二进制拆分“

目录 区别&#xff1a; 一句话说清楚&#xff1a; 板子&#xff1a; 区别&#xff1a; 得先懂完全背包问题完全背包问题 非零基础-CSDN博客 都是让背包内价值最大。 完全背包问题每种物品可以取无数次。而多重背包问题每件取的次数有限。 都可以用的最挫的方法就是0~k件去…...

nodejs微信小程序+python+PHP本科生优秀作业交流网站的设计与实现-计算机毕业设计推荐

通过软件的需求分析已经获得了系统的基本功能需求&#xff0c;根据需求&#xff0c;将本科生优秀作业交流网站功能模块主要分为管理员模块。管理员添加系统首页、个人中心、用户管理、作业分类管理、作业分享管理、论坛交流、投诉举报、系统管理等操作。 随着信息化社会的形成…...

使用git出现的问题

保证 首先保证自己的git已经下载 其次保证自己的gitee账号已经安装并且已经生成ssh公钥 保证自己要push的代码在要上传的文件夹内并且配置文件等都在父文件夹&#xff08;也就是文件没有套着文件&#xff09; 问题 1 $ git push origin master gitgitee.com: Permission de…...

rk3568 适配PCIE(二)

rk3568 适配pcie3.0 PCIe(Peripheral Component Interconnect Express)是一种用于连接计算机主板和其他设备的高速串行总线接口。PCIe 2.0和PCIe 3.0是两个不同版本的PCIe规范,它们在以下几个方面有所不同: 带宽:PCIe 2.0的理论带宽为每条通道5 Gbps,而PCIe 3.0的理论带…...

Java基础 进制

在Java中&#xff0c;可以使用不同的进制表示整数常量和字面量。 十进制&#xff08;Decimal&#xff09;&#xff1a;默认为十进制&#xff0c;不需要添加前缀。例如&#xff1a;int num 10;二进制&#xff08;Binary&#xff09;&#xff1a;以0b或0B作为前缀表示二进制。例…...

springboot中@Builder注解的详细用法实例,跟数据库结合。

在Spring Boot中&#xff0c;Builder注解是Lombok库提供的一个注解&#xff0c;用于生成带有Builder模式支持的构造器方法。通过Builder注解&#xff0c;可以简化对象的创建过程&#xff0c;特别适用于需要设置多个属性的情况。 下面是一个使用Builder注解的示例&#xff1a; …...

WT2605C蓝牙音频语音芯片:具备大功率IO驱动能力,引领音频技术新纪元

在当今的电子科技时代&#xff0c;功率强大的IO驱动能力成为音频设备性能的重要指标。近日&#xff0c;一款名为WT2605C的蓝牙音频语音芯片&#xff0c;以其最高可直接驱动64mA的大功率IO驱动能力&#xff0c;引起业界的广泛关注。这款芯片的出现&#xff0c;无疑将为音频设备的…...

【Java 基础】20 多线程操作方法

文章目录 1.获取和设置线程的名字1&#xff09;获取默认名字2&#xff09;获取自定义的名字 2.判断线程是否启动3.线程的强制执行4.让线程睡一会儿5.中断线程6.守护线程7.线程的礼让 前一节我们介绍了线程的定义、创建方法、状态以及各状态间的转换。在状态转换处只是简单的说明…...

SpringBoot使用mybatis-plus分页查询无效解决方案

问题概述 SpringBoot中使用mybatis-plus实现分页查询时&#xff0c;提供一个page分页对象和一个QueryWrapper条件类对象&#xff0c;在使用Service.page(page,queryWrapper)方法进行分页查询时&#xff0c;发现并未查询到分页的结果&#xff0c;反而是查询到全部符合条件的结果…...

QT 中 线程池 (备查)

QRunnable类 API 1&#xff09;在Qt中使用线程池需要先创建任务&#xff0c;添加到线程池中的每一个任务都需要是一个 QRunnable 类型&#xff0c;因此在程序中需要创建子类继承 QRunnable 这个类。 2&#xff09;然后重写 run() 方法&#xff0c;在这个函数中编写要在线程池中…...

LeetCode刷题笔记第71题:简化路径

LeetCode刷题笔记第71题&#xff1a;简化路径 题目 给定一个路径&#xff0c;简化路径 要求&#xff1a; 1、以’/‘开头 2、两个目录之间只有一个’/’ 3、不能以’/‘结尾 4、路径中不能有’.‘和’…’ 想法 利用栈的数据存储方式的思想&#xff0c;将路径字符顺序入栈遇…...

JavaScript <md5加密的两种不同输出结果分析>--案例(二点一)

前言: 问题是这样的,在浏览器中看到这段代码 然后在控制台进行输出.得到: 紧接着,就在,js文件里面进行转译: 可是,得到的结果是: 这是问题!!! 正题: 为什么相同的js代码,在 .js 文件中的输出与 Chrome 控制台中的输出不一样? 环境差异&#xff1a;不同的JavaScript环境&…...

『亚马逊云科技产品测评』活动征文|基于亚马逊EC2云服务器配置Nginx静态网页

授权声明&#xff1a;本篇文章授权活动官方亚马逊云科技文章转发、改写权&#xff0c;包括不限于在 Developer Centre, 知乎&#xff0c;自媒体平台&#xff0c;第三方开发者媒体等亚马逊云科技官方渠道 亚马逊EC2云服务器&#xff08;Elastic Compute Cloud&#xff09;是亚马…...

28、卷积 - 卷积的基础公式

本节推导一下卷积的基础公式,还是先上一张卷积运算的示意图图。 我们知道,一张图片有 3 个维度,分别是长、宽、通道。 这三个维度分别用 3 个字母代替,分别是 H(Height, 对应的是长这一维度), W(Width, 对应的是宽这一维度),C(Channel,对应的是通道这一维度)。 对于…...

Mac电脑vm虚拟机 VMware Fusion Pro中文 for mac

VMware Fusion Pro是一款功能强大的虚拟机软件&#xff0c;适用于需要在Mac电脑上运行其他操作系统的用户。它具有广泛的支持、快速稳定的特点以及多种高级功能&#xff0c;可以满足用户的各种需求和场景。 多操作系统支持&#xff1a;VMware Fusion Pro允许在Mac电脑上运行多…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...