专业网站有哪些平台,网站做等级保护,网站进行规划与设计,福清建设局网站简介2023-12-05每日一题
一、题目编号
2477. 到达首都的最少油耗二、题目链接
点击跳转到题目位置
三、题目描述
给你一棵 n 个节点的树#xff08;一个无向、连通、无环图#xff09;#xff0c;每个节点表示一个城市#xff0c;编号从 0 到 n - 1 #xff0c;且恰好有 …2023-12-05每日一题
一、题目编号
2477. 到达首都的最少油耗二、题目链接
点击跳转到题目位置
三、题目描述
给你一棵 n 个节点的树一个无向、连通、无环图每个节点表示一个城市编号从 0 到 n - 1 且恰好有 n - 1 条路。0 是首都。给你一个二维整数数组 roads 其中 roads[i] [ai, bi] 表示城市 ai 和 bi 之间有一条 双向路 。
每个城市里有一个代表他们都要去首都参加一个会议。
每座城市里有一辆车。给你一个整数 seats 表示每辆车里面座位的数目。
城市里的代表可以选择乘坐所在城市的车或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。
请你返回到达首都最少需要多少升汽油。
示例 1
示例 2
示例 3
四、解题代码
class Solution {
public:long long minimumFuelCost(vectorvectorint roads, int seats) {int n roads.size();vectorvectorint g(n 1);for (auto e : roads) {g[e[0]].push_back(e[1]);g[e[1]].push_back(e[0]);}long long res 0;functionint(int, int) dfs [](int cur, int fa) - int {int peopleSum 1;for (auto ne : g[cur]) {if (ne ! fa) {int peopleCnt dfs(ne, cur);peopleSum peopleCnt;res (peopleCnt seats - 1) / seats;}}return peopleSum;};dfs(0, -1);return res;}
};提示
1 n 105roads.length n - 1roads[i].length 20 ai, bi nai ! biroads 表示一棵合法的树。1 seats 105
五、解题思路
(1) 深度优先贪心
