<style>
/* 頁面整體設定 */
html, body, .ui-content {
background: #2C2C2C;
color: #00FFD5;
}
/* tag顏色設定 */
.markdown-body h6 {
font-size: .85em;
color: #A5FFE5;
-webkit-animation: discolor 5s linear infinite,
glint 2s ease infinite;
animation: discolor 5s linear infinite,
glint 2s ease infinite;
/*animation: discolor 5s linear infinite,
glint 2s ease infinite;*/
}
/* 設定右上角留言按鈕 */
#comment-app .open-comments {
background: transparent;
}
.btn-default {
background: transparent;
border-color: #A5FFE599;
-webkit-animation: discolor 5s linear infinite,
glint 2s ease infinite;
animation: discolor 5s linear infinite,
glint 2s ease infinite;
}
.btn-default:hover {
background: transparent;
}
.ui-comment-app .open-comments .btn.ui-open-comments {
color: #A5FFE599;
}
.ui-comment-app .open-comments .btn.ui-open-comments:hover {
color: #A5FFE5;
}
/* 設置愛心、收藏、小鈴鐺按鈕 */
.community-button {
color: #A5FFE580;
-webkit-animation: discolor 5s linear infinite,
glint 2s ease infinite;
animation: discolor 5s linear infinite,
glint 2s ease infinite;
}
.community-button:hover {
color: #A5FFE5;
background: transparent;
}
/* 設定 code 模板 */
.markdown-body code,
.markdown-body tt {
background-color: #ffffff36;
}
.markdown-body .highlight pre,
.markdown-body pre {
color: #ddd;
background-color: #00000080;
}
.hljs-tag {
color: #ddd;
}
.token.operator {
background-color: transparent;
}
/* h1, h2 樣式 */
.markdown-body h1,
.markdown-body h2 {
border-bottom-color: #ffffff80;
text-shadow: 3px 3px 3px #009B67;
}

/* 設定小目錄的背景顏色 */
.ui-toc-dropdown {
background-color: #2C2C2C;
}
/* 設定行動裝置中，小目錄按鈕 */
.ui-toc-label.btn {
background: linear-gradient(180deg, #2BE8CF60 0%, #2B83E860 100%);
color: #ffffff90;
}
.ui-toc-label.btn:hover {
background: linear-gradient(180deg, #2BE8CF90 0%, #2B83E890 100%);
color: #ffffff;
}
/* 設定小目錄內連結 */
.ui-toc-dropdown .nav>li>a,
.toc-menu>a {
color: #D4F9FF;
font-weight: bold;
}
.ui-toc-dropdown .nav>li>a:focus,
.ui-toc-dropdown .nav>li>a:hover {
color: #00FFD5;
border-left: 1px solid #00FFD5;
}

.ui-toc-dropdown .nav>.active:focus>a,
.ui-toc-dropdown .nav>.active:hover>a,
.ui-toc-dropdown .nav>.active>a {
color: #00FFD5;
border-left: 1px solid #00FFD5;
/* -webkit-animation: discolor 5s linear infinite,
glint 2s ease infinite;
animation: discolor 5s linear infinite,
glint 2s ease infinite; */
}

.toc-menu>a:focus,
.toc-menu>a:hover {
color: #00FFD5;
}
/* 回到最上面的按鈕 */
.markdown-body a > .fa-chevron-up {
position: fixed;
bottom: 20px;
right: 20px;
padding: 4px;
border-radius: 4px;
color: #fff;
background: linear-gradient(180deg, #2BE8CF60 0%, #2B83E860 100%);
}
.markdown-body a:hover > .fa {
background: linear-gradient(180deg, #2BE8CF95 0%, #2B83E895 100%);
-webkit-animation: discolor 5s linear infinite,
glint 2s ease infinite;
animation: discolor 5s linear infinite,
glint 2s ease infinite;
}
/* 右邊滾動軸 */
::-webkit-scrollbar {
width: 10px;
}
::-webkit-scrollbar-track {
background: transparent;
}
::-webkit-scrollbar-thumb {
background: linear-gradient(180deg, #2BE8CF60 0%, #2B83E860 100%);
border-radius: 3px;
}
::-webkit-scrollbar-thumb:hover {
background: linear-gradient(180deg, #2BE8CF95 0%, #2B83E895 100%);
}
/* 設定連結 */
a,
.open-files-container li.selected a {
color: #89FFF8;

}
a:hover,
.open-files-container li.selected a:hover {
color: #89FFF8;
}
/* 上面的名字顏色修改 */
.text-gray-900 {
--tw-text-opacity: 1;
color: #95FFFF;
animation: discolor 5s linear infinite,
glint 2s ease infinite;
}

/* 下面的名字顏色修改 */
/* 這個會修改到最下面的HackMD 但不會閃爍*/
.footer a {
color: #95FFFF;
}
.text-black-brand {
--tw-text-opacity: 1;
animation: discolor 5s linear infinite,
glint 2s ease infinite;
}
/* 動畫 */
@keyframes discolor {
0%, 100% {filter: hue-rotate(0);}
50% {filter: hue-rotate(180deg);}
}
</style>

###### tags: `LeetCode`
# 2477. Minimum Fuel Cost to Report to the Capital

## 題目
計算每個城市的代表到首都要花多少公升的汽油。
1. seats是每台車的座位數
2. 可以換車或跟其他代表坐同一台車
3. 兩個城市之間要花一公升的汽油

<a href = "https://leetcode.com/problems/minimum-fuel-cost-to-report-to-the-capital/description/"><i class=" fa fa-bug"></i> 題目連結</a>

## 程式碼

class Solution {
public:
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) 
    {
        ans = 0;
        const int n = roads.size() + 1;    //城市數
        visited = vector<bool>(n, false);    //是否走過
        vector<vector<int>> adj(n, vector<int>());    //相鄰串列
        for(vector<int> r : roads)    //建相鄰矩陣
        {
            adj[r[0]].push_back(r[1]);
            adj[r[1]].push_back(r[0]);
        }
        dfs(0, adj, seats);    //DFS
        return ans;
    }
private:
    vector<bool> visited;
    long long ans;
    pair<int, int> dfs(int now, vector<vector<int>> &adj, int &seats)
    //now：現在的城市，回傳的pair：{車數, 剩餘座位}
    {
        visited[now] = true;    //設成已走過
        const int size = adj[now].size();
        int car = 0, left = 0;    //car：總車數，left：剩餘座位
        for(int i = 0;i < size;i ++)    
        //走訪相鄰的城市，並計算到這個城市的車數和剩餘座位
        {
            if(!visited[adj[now][i]])    //如果沒走過
            {
                auto [c, l] = dfs(adj[now][i], adj, seats);
                car += c;
                left += l;
            }
        }
        ans += car;    //加上從上個城市到現在城市的汽油
        
        //處理現在城市的代表
        if(left == 0)    //如果沒座位了   
        {
            car ++;    //加一台車
            left = seats - 1;
        }
        else
            left --;    //減少一個座位
        if(left >= seats)    //併車
        {
            car -= left / seats;
            left %= seats;
        }
        return pair<int, int> {car, left};
    }
};

改良版

class Solution {
public:
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) 
    {
        ans = 0;
        const int n = roads.size() + 1;    //城市數
        visited = vector<bool>(n, false);    //是否走過
        vector<vector<int>> adj(n, vector<int>());    //相鄰串列
        for(vector<int> r : roads)    //建相鄰矩陣
        {
            adj[r[0]].push_back(r[1]);
            adj[r[1]].push_back(r[0]);
        }
        dfs(0, adj, seats);    //DFS
        return ans;
    }
private:
    vector<bool> visited;
    long long ans;
    int dfs(int now, vector<vector<int>> &adj, int &seats)
    //now：現在的城市
    {
        visited[now] = true;    //設成已走過
        const int size = adj[now].size();
        
        int people = 0;    //計算從這個城市出發的人數
        for(int i = 0;i < size;i ++)
            if(!visited[adj[now][i]])
                people += dfs(adj[now][i], adj, seats);
        people ++;    //加這個城市的代表
        
        if(now != 0)    //如果不是在首都
            ans += people / seats + (people % seats != 0);
            //加上到下一個城市所需的汽油
        
        return people;
    }
};

寫到快睡著Q
## DATE

2023/02/12