Leetcode—2477.到达首都的最少油耗【中等】
2023每日刷题（五十）
Leetcode—2477.到达首都的最少油耗
算法思想
参考自灵茶山艾府
实现代码
class Solution {
public:
long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
int n = roads.size() + 1;
vector<int> g[n];
for(auto &e: roads) {
int x = e[0], y = e[1];
g[x].emplace_back(y);
g[y].emplace_back(x);
}
long long ans = 0;
function<int(int, int)> dfs = [&](int x, int fa) {
int sze = 1;
for(auto y: g[x]) {
if(y != fa) {
sze += dfs(y, x);
}
}
// x 不是根节点
if(x) {
// (sze / seats)向上取整
ans += (sze - 1) / seats + 1;
}
return sze;
};
dfs(0, -1);
return ans;
}
};
运行结果
之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！