当前位置：首页 > article >正文

【算法思考记录】力扣2477. 到达首都的最少油耗【JavaScript，深度优先搜索】

article 2024/11/16 14:59:50

原题链接

到达首都的最少油耗：一种优雅的解决方案

题目解析

这个算法题目描述了一个有趣的场景：一棵由城市和道路组成的树形结构，其中每个节点代表一个城市，边代表道路。所有城市的代表需要前往编号为0的城市——首都参加会议。任务是计算代表们到达首都所需的最小油耗，假设每座城市只有一辆车，且每辆车的座位数相同。

输入说明

roads: 一个二维数组，表示城市间的双向道路。
seats: 整数，表示每辆车的座位数。

输出说明

返回一个整数，表示最小的油耗总量。

题解思路

这个问题可以转化为遍历树的问题。对于树中的每一个非首都节点，计算它的子树中有多少个节点，并将这个数除以座位数向上取整，得到的就是从该节点到首都所需的最少油耗。最后，将所有这些油耗相加即可。

JavaScript 代码实现

var minimumFuelCost = function (roads, seats) {
    const graph = Array(roads.length + 1).fill(null).map(() => []);
    for (const [x, y] of roads) {
        graph[x].push(y); // 记录每个点的邻居
        graph[y].push(x);
    }

    let ans = 0;
    function dfs(x, fa) {
        let size = 1;
        for (const y of graph[x]) {
            if (y !== fa) { // 递归子节点，不能递归父节点
                size += dfs(y, x); // 统计子树大小
            }
        }
        if (x !== 0) { // x 不是根节点
            ans += ((size - 1) / seats | 0) + 1;
        }
        return size;
    }
    dfs(0, -1);
    return ans;
};