2285. Maximum Total Importance of Roads

這題目的要點如下:

1. 你有 n 個城市和一些連接城市的道路。
2. 你需要給每個城市分配一個從 1 到 n 的重要性值,每個數字只能用一次。
3. 一條道路的重要性是它連接的兩個城市的重要性值之和。
4. 你的目標是最大化所有道路的重要性總和。

解題思路:

1. 關鍵觀察:連接度(即與其他城市相連的道路數)較高的城市應該獲得較高的重要性值。
2. 計算每個城市的連接度。
3. 根據連接度對城市進行排序。
4. 將最高的重要性值(n)分配給連接度最高的城市,次高的重要性值(n-1)分配給連接度次高的城市,以此類推。
5. 計算所有道路的重要性總和。

這種方法可以保證獲得最大的總重要性,因為它確保了連接度高的城市獲得高的重要性值,從而最大化了每條道路的貢獻。

#define ll long long

class Solution {
public:
    long long maximumImportance(int n, vector<vector<int>>& roads)
    {
        vector<ll> city(n);
        // 計算與多少城市相連
        for(auto road : roads)
        {
            city[road[0]]++;
            city[road[1]]++;
        }

        sort(city.begin(), city.end());

        ll res = 0;
        // city = [1, 2, 2, 3, 4]
        //         1, 2, 3, 4, 5
        //         1 + 4 + 6 + 12 + 20 = 43
        // res += 與多少城市相連 * 城市的數目加權
        for (int i = 0; i < n; ++i)
        {
            res += (i + 1) * city[i];
        }
        return res;
    }
};

• T: $O(n^2)$
• S: $O(n)$