Every day a Leetcode

題目來源：2477. 到達首都的最少油耗

解法1：貪心 + 深度優先搜索

題目等價于給出了一棵以節點 0 為根結點的樹，并且初始樹上的每一個節點上都有一個人，現在所有人都需要通過「車子」向結點 0 移動。

對于某一個節點 x（x 不等于 0），其父節點為 y，因為以節點 x 為根節點的子樹上的人都需要通過邊 x->y 向節點 0 移動，所以為了使這條邊上的「車子」利用率最高，我們貪心的讓 x 的全部子節點上的人到了節點 x 再一起坐車向上移動，我們不妨設以節點 x 為根節點的子樹大小為 cnt_x，那么我們至少需要「車子」的數量為?cnt_x/seats?，其中 seats 是每輛車里面座位的數目。

那么我們可以通過從根結點 0 往下進行「深度優先搜索」，每一條邊上「車子」的數目即為該條邊上汽油的開銷，統計全部邊上汽油的開銷即為最終答案。

示例：

代碼：

/** @lc app=leetcode.cn id=2477 lang=cpp** [2477] 到達首都的最少油耗*/// @lc code=start
class Solution
{
private:long long ans = 0;public:long long minimumFuelCost(vector<vector<int>> &roads, int seats){// 特判if (roads.empty() || seats == 0)return 0;int n = roads.size();vector<vector<int>> edges(n + 1);for (vector<int> &road : roads){int from = road[0], to = road[1];// 記錄每個點的鄰居edges[from].push_back(to);edges[to].push_back(from);}function<int(int, int)> dfs = [&](int x, int father) -> int{int subTreeSize = 1;for (int &y : edges[x])if (y != father) // 遞歸子節點，不能遞歸父節點{// 統計子樹大小subTreeSize += dfs(y, x);}if (x != 0) // x 不是根節點ans += ceil(1.0 * subTreeSize / seats);return subTreeSize;};dfs(0, -1);return ans;}
};
// @lc code=end

結果：

復雜度分析：

時間復雜度：O(n)，其中 n 是數組 roads 的長度。遞歸這棵樹，每個節點至多訪問一次。

空間復雜度：O(n)，其中 n 是數組 roads 的長度。