Leetcode 2477. Minimum Fuel Cost to Report to the Capital

[Woodyiiiiiii]

这道题我并没有什么思路，想到car数量不够会怎样，如何一次性convey所有人，如何分配car，如何计算fuel。

但要知道，graph，tree类型的问题，solution都是整治法化为一个个小问题，然后积累解决。

正解：

1. 预处理，得到节点之间的连接关系(图的先处理)
2. DFS，从末端节点开始计算以其为根的所有人数(经典DFS/BFS)
3. 分配car，用Math.ceil取整使得car能装载最多人数(节点之间的人的移动是car的数量，且不会出现car不够的情况)
4. 一步递归一个fuel，以此往上层递进

class Solution {
    
    long ans = 0;

    public long minimumFuelCost(int[][] roads, int seats) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= roads.length; ++i) {
            graph.add(new ArrayList<>());
        }
        // build graph
        for (int[] road : roads) {
            graph.get(road[0]).add(road[1]);
            graph.get(road[1]).add(road[0]);
        }

        // dfs
        dfs(graph, 0, 0, seats);

        return ans;
    }

    private int dfs(List<List<Integer>> graph, int i, int prev, int seats) {
        int people = 1;
        for (int j : graph.get(i)) {
            if (j != prev) {
                people += dfs(graph, j, i, seats);
            }
        }
        
        if (i != 0) {
            ans += Math.ceil(people * 1.0 / seats);
        }

        return people;
    }
    
}

---

• https://leetcode.com/problems/minimum-fuel-cost-to-report-to-the-capital/