【每日一题】到达首都的最少油耗

文章目录

Tag
题目来源
题目解读
解题思路
- 方法一：贪心+深搜
写在最后

Tag

【递归/深度优先搜索】【树】【2023-12-05】

题目来源

2477. 到达首都的最少油耗

题目解读

每个城市都有一位代表需要前往城市 0 进行开会。每个城市都有一辆座位数为 seats 的汽车，代表可以选择乘坐所在城市的车，或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。

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

解题思路

方法一：贪心+深搜

思路

本题等价于给出了一棵根节点为 0 的树，树的每个节点上都有一个人，所有都需要通过汽车来到根节点 0。

为了消耗最少的汽油，一定要尽可能的拼车。

于是可以从最外围的城市节点向 0 城市进发，每到达一个城市节点能拼车一定要拼车，于是需要统计每个城市节点 x 的子城市节点数，计算到达城市节点 x 的人数 peopleCnt。

到达城市节点 x 的最小油耗为

$\lceil{\frac{peopleCnt}{seats}}\rceil$

比如示例 2 的 2-3-1-0 段：

从城市 2 到城市 3 最少耗油 1 升，因为无人拼车；
从城市 3 到城市 1 最少耗油 1 升，因为目前到达城市 3 的有两人（到达一人+城市本身有一人），可以拼座位数为 2 的车，所以最小耗油 1 升；
从城市 1 到城市 0 最少耗油 2 升，因为目前到达城市 0 的有三人（到达两人+城市本身有一人），其中两人可以拼座位数为 2 的车，另外一个人需单独乘车，所以最小油耗为 2；
最后累加得到 2-3-1-0 段最小油耗为 4。

于是可以利用深度优先搜索的方法，从根节点即城市 0 深搜累加最小油耗得到最终答案。

算法

首先根据数组 roads 建立无向图 g，g[x] 表示的是与城市 x 相连的所有城市数组。

接着从根节点即城市 0 出发，进行深度优先搜索，在深搜的过程中更新答案 res，最后返回 res。

深搜的递归函数为 dfs，当前的城市为 x，其父节点城市为 fa：

递归出口为当前城市不再有任何子节点城市，直接返回 peopleSum = 1；
如果当前城市有子节点城市，遍历所有的子节点城市 y，得到从城市 y 到达当前城市的人数 peopleCnt，计算 (peopleCnt + seats - 1) / seats 得到从城市 y 到达当前城市的最小油耗，并到答案 res 中。并更新到达当前城市的人数 peopleSum += peopleCnt，最后返回 peopleSum。

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

        for (auto road : roads) {
            int x = road[0], y = road[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }
        long long res = 0;
        function<int(int, int)> dfs = [&](int x, int fa) -> int {
            int peopleSum = 1;
            for (auto y : g[x]) {
                if (y != fa) {
                    int peopleCnt = dfs(y, x);
                    res += (peopleCnt + seats - 1) / seats;
                    peopleSum += peopleCnt;
                }
            }
            return peopleSum;
        };
        dfs(0, -1);
        return res;
    }
};