Skip to content

Latest commit

 

History

History
222 lines (175 loc) · 6.49 KB

README.md

File metadata and controls

222 lines (175 loc) · 6.49 KB

2477. 到达首都的最少油耗

English Version

题目描述

给你一棵 n 个节点的树（一个无向、连通、无环图），每个节点表示一个城市，编号从 0 到 n - 1 ，且恰好有 n - 1 条路。0 是首都。给你一个二维整数数组 roads ，其中 roads[i] = [ai, bi] ，表示城市 ai 和 bi 之间有一条 双向路 。

每个城市里有一个代表，他们都要去首都参加一个会议。

每座城市里有一辆车。给你一个整数 seats 表示每辆车里面座位的数目。

城市里的代表可以选择乘坐所在城市的车，或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。

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

 

示例 1：

输入：roads = [[0,1],[0,2],[0,3]], seats = 5
输出：3
解释：
- 代表 1 直接到达首都，消耗 1 升汽油。
- 代表 2 直接到达首都，消耗 1 升汽油。
- 代表 3 直接到达首都，消耗 1 升汽油。
最少消耗 3 升汽油。

示例 2：

输入：roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 2
输出：7
解释：
- 代表 2 到达城市 3 ，消耗 1 升汽油。
- 代表 2 和代表 3 一起到达城市 1 ，消耗 1 升汽油。
- 代表 2 和代表 3 一起到达首都，消耗 1 升汽油。
- 代表 1 直接到达首都，消耗 1 升汽油。
- 代表 5 直接到达首都，消耗 1 升汽油。
- 代表 6 到达城市 4 ，消耗 1 升汽油。
- 代表 4 和代表 6 一起到达首都，消耗 1 升汽油。
最少消耗 7 升汽油。

示例 3：

输入：roads = [], seats = 1
输出：0
解释：没有代表需要从别的城市到达首都。

 

提示：

  • 1 <= n <= 105
  • roads.length == n - 1
  • roads[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • roads 表示一棵合法的树。
  • 1 <= seats <= 105

解法

方法一：DFS

建图，然后用 DFS 统计以每个点为根的子树的节点个数，假设以 $a$ 为根的子树中有 $size$ 个节点，那么到达根节点一共需要 $\lceil \frac{size}{seats} \rceil$ 辆车。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为节点个数。

Python3

class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        def dfs(a, fa):
            size = 1
            for b in g[a]:
                if b != fa:
                    t = dfs(b, a)
                    nonlocal ans
                    ans += (t + seats - 1) // seats
                    size += t
            return size

        g = defaultdict(list)
        for a, b in roads:
            g[a].append(b)
            g[b].append(a)
        ans = 0
        dfs(0, -1)
        return ans

Java

class Solution {
    private List<Integer>[] g;
    private long ans;
    private int seats;

    public long minimumFuelCost(int[][] roads, int seats) {
        int n = roads.length + 1;
        g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        this.seats = seats;
        for (var e : roads) {
            int a = e[0], b = e[1];
            g[a].add(b);
            g[b].add(a);
        }
        dfs(0, -1);
        return ans;
    }

    private int dfs(int a, int fa) {
        int size = 1;
        for (int b : g[a]) {
            if (b != fa) {
                int t = dfs(b, a);
                ans += (t + seats - 1) / seats;
                size += t;
            }
        }
        return size;
    }
}

C++

class Solution {
public:
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        int n = roads.size() + 1;
        vector<vector<int>> g(n);
        for (auto& e : roads) {
            int a = e[0], b = e[1];
            g[a].emplace_back(b);
            g[b].emplace_back(a);
        }
        long long ans = 0;
        function<int(int, int)> dfs = [&](int a, int fa) -> int {
            int size = 1;
            for (int b : g[a]) {
                if (b != fa) {
                    int t = dfs(b, a);
                    ans += (t + seats - 1) / seats;
                    size += t;
                }
            }
            return size;
        };
        dfs(0, -1);
        return ans;
    }
};

Go

func minimumFuelCost(roads [][]int, seats int) int64 {
	n := len(roads) + 1
	g := make([][]int, n)
	for _, e := range roads {
		a, b := e[0], e[1]
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}
	ans := 0
	var dfs func(int, int) int
	dfs = func(a, fa int) int {
		size := 1
		for _, b := range g[a] {
			if b != fa {
				t := dfs(b, a)
				ans += (t + seats - 1) / seats
				size += t
			}
		}
		return size
	}
	dfs(0, -1)
	return int64(ans)
}

TypeScript



...