leetcode 2285. 道路的最大总重要性

题目描述

给你一个整数 n ，表示一个国家里的城市数目。城市编号为 0 到 n - 1 。

给你一个二维整数数组 roads ，其中 roads[i] = [a_i, b_i] 表示城市 a_i 和 b_i 之间有一条双向道路。

你需要给每个城市安排一个从 1 到 n 之间的整数值，且每个值只能被使用一次。道路的 重要性 定义为这条道路连接的两座城市数值之和。

请你返回在最优安排下，所有道路重要性 之和最大为多少。

示例 1：

输入：n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
输出：43
解释：上图展示了国家图和每个城市被安排的值 [2,4,5,3,1] 。
- 道路 (0,1) 重要性为 2 + 4 = 6 。
- 道路 (1,2) 重要性为 4 + 5 = 9 。
- 道路 (2,3) 重要性为 5 + 3 = 8 。
- 道路 (0,2) 重要性为 2 + 5 = 7 。
- 道路 (1,3) 重要性为 4 + 3 = 7 。
- 道路 (2,4) 重要性为 5 + 1 = 6 。
所有道路重要性之和为 6 + 9 + 8 + 7 + 7 + 6 = 43 。
可以证明，重要性之和不可能超过 43 。

示例 2：

输入：n = 5, roads = [[0,3],[2,4],[1,3]]
输出：20
解释：上图展示了国家图和每个城市被安排的值 [4,3,2,5,1] 。
- 道路 (0,3) 重要性为 4 + 5 = 9 。
- 道路 (2,4) 重要性为 2 + 1 = 3 。
- 道路 (1,3) 重要性为 3 + 5 = 8 。
所有道路重要性之和为 9 + 3 + 8 = 20 。
可以证明，重要性之和不可能超过 20 。

提示：

2 <= n <= 5 * 10⁴
1 <= roads.length <= 5 * 10⁴
roads[i].length == 2
0 <= a_i, b_i <= n - 1
a_i != b_i
没有重复道路。

题解——哈希表

思路

用ri表示道路,ci表示城市,cnt表示城市连接的道路数,则道路重要性之和可以这样表示

所以道路重要性之和可以转化为城市重要性之和,考虑如何得到最大的城市重要性之和
每个城市的重要性=ci*cnt,由于ci是我们赋值的,所以给较大的cnt赋较大的ci,可以使答案最大

构建一个哈希表,储存每个城市连接的道路数，然后将哈希表转化成数组,并根据value排序,得到从大到小的顺序，从n开始赋值,每次递减,乘以cnt,加到ans上,就得到了答案，注意,由于答案可能很大,应该转化为long long

代码

class Solution {
public:
    long long maximumImportance(int n,vector<vector<int>>& roads) {
        unordered_map<int,int> roadCnt;//记录城市连接的道路数
        long long ans=0;
        for (int i=0;i<roads.size();++i)
        {
            ++roadCnt[roads[i][0]];//第一个城市++
            ++roadCnt[roads[i][1]];//第二个城市++
        }
        vector<pair<int,int>> vec(roadCnt.begin(),roadCnt.end());//哈希表转数组
        sort(vec.begin(),vec.end(),[](auto pr1, auto pr2){return pr1.second>pr2.second;});//按value倒序排列
        for (int i=0;i<vec.size();++i)//赋值并求和
            ans+=(long long)vec[i].second*(n--);
        return ans;
    }
};