Re: [閒聊] 每日LeetCode已回收
2477. Minimum Fuel Cost to Report to the Capital
給一棵 tree，有 n 個點代表 n 個城市，
每座城市都有一台車可以通往其他的城市，
通過每條邊會消耗 1 單位的油，
一台車最多可以一次載 seats 個人，
現在每座城市都有 1 個人要到 0 號城市，求最少需要幾單位的油。
Example 1:
Input: roads = [[0, 1], [0, 2], [0, 3]], seats = 5
Output: 3
Explanation:
https://i.imgur.com/tIgPJaJ.png
1、2、3 號城市各需要 1 台車通往 0 號城市。
Example 2:
Input: roads = [[3, 1], [3, 2], [1, 0], [0, 4], [0, 5], [4, 6]], seats = 2
Output: 7
Explanation:
https://i.imgur.com/1VnMzZn.png
把每條邊的值加一加就能得到 7
Example 3:
Input: roads = [], seats = 1
Output: 0
Explanation:
只有 0 號點存在，不需要任何車
解題思路：
從 0 號點開始進行 DFS，數每條連出去的邊各自有多少 children，
由於可以並車，多個人到同個城市後改搭同班車降低油耗，
把 children 的個數除以 seats 後取上高斯就是這條邊至少需要多少台車通過，
然後每條邊加一加就是全部需要多少單位的油。
C++ code:
class Solution {
public:
long long dfs(const vector<vector<int>> &edge, int id, int parent, long
long &ans, int seats){
int sum = 0;
for(auto to : edge[id]){
if(to == parent) continue;
long long res = dfs(edge, to, id, ans, seats);
sum += res;
ans += ceil((double)res / seats);
}
return sum + 1;
}
long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
vector<vector<int>> edge(roads.size() + 1);
for(auto e : roads){
edge[e[0]].push_back(e[1]);
edge[e[1]].push_back(e[0]);
}
long long ans = 0;
dfs(edge, 0, -1, ans, seats);
return ans;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.229.216 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1676161807.A.E69.html
推
02/12 11:47,
2年前
, 1F
02/12 11:47, 1F
最近作息都很早起 不知道還能維持幾天
※ 編輯: idiont (140.113.229.216 臺灣), 02/12/2023 12:25:28
※ 編輯: idiont (140.113.229.216 臺灣), 02/12/2023 23:01:02
討論串 (同標題文章)
完整討論串 (本文為第 229 之 719 篇)：