数码设计网站,电子产品开发流程8个步骤,动漫制作专业笔记本电脑推荐,做美食的网站3妹#xff1a;“太阳当空照#xff0c;花儿对我笑#xff0c;小鸟说早早早#xff0c;你为什么背上炸药包” 2哥 :3妹#xff0c;什么事呀这么开发。 3妹#xff1a;2哥你看今天的天气多好啊#xff0c;阳光明媚、万里无云、秋高气爽#xff0c;适合秋游。 2哥#x…
3妹“太阳当空照花儿对我笑小鸟说早早早你为什么背上炸药包” 2哥 :3妹什么事呀这么开发。 3妹2哥你看今天的天气多好啊阳光明媚、万里无云、秋高气爽适合秋游。 2哥是啊立冬之后天气多以多云为主好不容易艳阳高照。可是你不能秋游赶紧收拾收拾上班去啦 3妹哼 好吧~ 2哥给你出了一道题发你微信里了 上班通勤的路上记得看一下回来问你答案~ 3妹知道啦难不倒我
题目
给你一棵 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 10^5 roads.length n - 1 roads[i].length 2 0 ai, bi n ai ! bi roads 表示一棵合法的树。 1 seats 10^5
思路 贪心 深度优先搜索, 题目等价于给出了一棵以节点 0 为根结点的树并且初始树上的每一个节点上都有一个人现在所有人都需要通过「车子」向结点 0 移动。
对于某一个节点 xx≠0其父节点为 y。因为以节点 x 为根结点的子树上的人都需要通过边 x→y向节点 0 移动所以为了使这条边上的「车子」利用率最高我们贪心的让 x 的全部子节点上的人到了节点 x 后再一起坐车向上移动我们不妨设以节点 x 为根节点的子树大小为 cntx那么我们至少需要「车子」的数量为 ⌈cntx/seats⌉其中 seats 为一辆车的给定座位数。
那么我们可以通过从根结点 0 往下进行「深度优先搜索」每一条边上「车子」的数目即为该条边上汽油的开销统计全部边上汽油的开销即为最终答案。
java代码
class Solution {long ans 0;public long minimumFuelCost(int[][] roads, int seats) {int n roads.length 1;ListListInteger map new ArrayList();for (int i 0; i n; i) {map.add(new ArrayList());}for (int i 0; i roads.length; i) {map.get(roads[i][0]).add(roads[i][1]);map.get(roads[i][1]).add(roads[i][0]);}dfs(map,0,-1,seats);return ans;}public int dfs(ListListInteger map,int cur,int father,int seats){int size 1;for (int node : map.get(cur)){if (node ! father){size dfs(map,node,cur,seats);}}if (cur ! 0) ans(int)Math.ceil((double) size/seats);return size;}
}
