题目描述
leetcode 中等题
给你一棵 n 个节点的树（一个无向、连通、无环图），每个节点表示一个城市，编号从 0 到 n - 1 ，且恰好有 n - 1 条路。0 是首都。给你一个二维整数数组 roads ，其中 roads[i] = [ai, bi] ，表示城市 ai 和 bi 之间有一条 双向路 。
每个城市里有一个代表，他们都要去首都参加一个会议。
每座城市里有一辆车。给你一个整数 seats 表示每辆车里面座位的数目。
城市里的代表可以选择乘坐所在城市的车，或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。
请你返回到达首都最少需要多少升汽油。
示例1：
1
2
3
4
5
6
7
| 输入：roads = [[0,1],[0,2],[0,3]], seats = 5
输出：3
解释：
- 代表 1 直接到达首都，消耗 1 升汽油。
- 代表 2 直接到达首都，消耗 1 升汽油。
- 代表 3 直接到达首都，消耗 1 升汽油。
最少消耗 3 升汽油。
|
示例2:
1
2
3
4
5
6
7
8
9
10
11
| 输入：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：
1
2
3
| 输入：roads = [], seats = 1
输出：0
解释：没有代表需要从别的城市到达首都。
|
提示1：
1
2
3
4
5
6
7
| 1 <= n <= 105
roads.length == n - 1
roads[i].length == 2
0 <= ai, bi < n
ai != bi
roads 表示一棵合法的树。
1 <= seats <= 105
|
贪心
车辆可以视为无限的，要使消耗的油最少，可以递归的判断对于每个子节点，汇集到该节点的人一共有多少，那么也就是该节点的子节点数量 $count$，并且每次都可以取汇集到该节点的所有人到下一个节点最少需要花费的油量 $ceil(\frac{count}{seats})$ 视为该节点的贡献，最后累加所有节点的贡献就为答案。
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
30
31
32
33
34
| class Solution {
List<Integer>[] g;
int seats;
long ans;
public long minimumFuelCost(int[][] roads, int seats) {
if(roads.length == 0){
return 0;
}
this.seats = seats;
g = new List[roads.length + 1];
IntStream.range(0, roads.length + 1).forEach(i -> g[i] = new ArrayList<>());
for(int[] road : roads){
g[road[0]].add(road[1]);
g[road[1]].add(road[0]);
}
dfs(0, -1);
return ans;
}
private long dfs(int p, int father){
long size = 1;
for(int item : g[p]){
if(item == father){
continue;
}
size += dfs(item, p);
}
if(p != 0){
ans += Math.ceil((double)size / seats);
}
return size;
}
}
|