LC 6243 到达首都的最少油耗(贪心)

LC 6243 到达首都的最少油耗(贪心)

需要考虑每条边的贡献，下界是$\lceil \frac{sz}{seat}\rceil$，$sz$是该子树大小。

上界其实等于下界，因为在其他人到达该子树根之后，可以只用这么多辆车就够了，其他车不需要了。

因此就是dfs一下即可。

时间复杂度：$O(n)$

class Solution {
public:
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        int n = roads.size() + 1;

        // 建图
        vector<int> e[n];
        for (auto &road : roads) {
            e[road[0]].push_back(road[1]);
            e[road[1]].push_back(road[0]);
        }

        long long ans = 0;
        // DFS 统计子树大小，同时统计答案
        function<int(int, int)> dfs = [&](int sn, int fa) {
            int ret = 1;
            for (int fn : e[sn]) if (fn != fa) {
                // 计算 sn -> fn 这条边的贡献
                int t = dfs(fn, sn);
                ans += (t + seats - 1) / seats;
                // 更新子树大小
                ret += t;
            }
            return ret;
        };
        dfs(0, -1);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29