🔗 🟡 2285. Maximum Total Importance of Roads 1496

tags: `Biweekly Contest 79` `圖(Graph)` `貪心(Greedy)` `排序(Sorting)` `堆積(Heap)`

題意

給定一個整數 $n$ ，表示一個國家的城市數量。這些城市從 $0$ 到 $n-1$ 編號。

另給定一個二維整數陣列 $\text{roads}$ ，其中 $\text{roads}[i] = [a_i, b_i]$ 表示存在一條連接城市 $a_i$ 和 $b_i$ 的雙向道路。

您需要為每個城市分配一個整數值從 $1$ 到 $n$ ，每個值只能使用一次。然後，一條路的重要程度被定義為它連接的兩個城市的值的總和。

在最佳情況下分配值後，返回所有可能路的 最大總重要程度 。

思路：貪心(Greedy) + 排序(Sorting)

從城市的角度思考，如果一個城市有 $x$ 條道路連接，且被分配到的整數是 $w$ ，則這個城市的重要程度為 $x \times w$ 。

對於連接道路數量最多的城市，我們希望它被分配到最大的整數，這樣可以使答案最大。連接道路數量次多的城市被分配到次大的整數，以此類推。

為此可以先計算每個城市的連接道路數量，即統計其度數(degree) ，然後將度數排序(Sorting) ，將最大的度數對應到最大的整數，次大的度數對應到次大的整數，以此類推。

複雜度分析

時間複雜度： $\mathcal{O}(n \log n)$ ，其中 $n$ 為城市數量。
空間複雜度： $\mathcal{O}(n)$ 。

class Solution:
    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
        deg = [0] * n
        for u, v in roads:
            deg[u] += 1
            deg[v] += 1
        deg.sort()
        ans = 0
        for i, x in enumerate(deg, 1):
            ans += x * i
        return ans

class Solution {
public:
    long long maximumImportance(int n, vector<vector<int>>& roads) {
        vector<int> deg(n, 0);
        for (auto e : roads) {
            deg[e[0]]++;
            deg[e[1]]++;
        }
        sort(deg.begin(), deg.end());
        long long ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += (long long) i * deg[i-1];
        }
        return ans;
    }
};