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(vector<vector<int>>& roads, int seats) {int n = roads.size();vector<vector<int>> 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;function<int(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 <= 10⁵
• roads.length == n - 1
• roads[i].length == 2
• 0 <= a_i, b_i < n
• a_i != b_i
• roads 表示一棵合法的树。
• 1 <= seats <= 10⁵

五、解题思路

(1) 深度优先+贪心