golang刷leetcode:道路的最大总重要性

共 1673字,需浏览 4分钟

 ·

2022-06-27 23:39

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

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

你需要给每个城市安排一个从 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 * 104

  • 1 <= roads.length <= 5 * 104

  • roads[i].length == 2

  • 0 <= ai, bi <= n - 1

  • ai != bi

  • 没有重复道路。

解题思路:

1,本题的关键在于如何给每个节点安排值

2,如果要和最大,需要把值最大的节点计算更多次

3,因此我们统计每个节点的度

4,一个节点的值被计算的次数就是它的度


import("sort")func maximumImportance(n int, roads [][]int) int64 {    adj:=make(map[int]int)    for _,r:=range roads{        adj[r[0]]++        adj[r[1]]++    }    arr:=make([]int,len(adj))    i:=0    for _,v:=range adj{        arr[i]=v        i++    }    sort.Ints(arr)    sum:=0    num:=n    for i:=len(arr)-1;i>=0;i--{        sum+=arr[i]*num        num--    }    return int64(sum)}


推荐阅读


福利

我为大家整理了一份从入门到进阶的Go学习资料礼包,包含学习建议:入门看什么,进阶看什么。关注公众号 「polarisxu」,回复 ebook 获取;还可以回复「进群」,和数万 Gopher 交流学习。

浏览 31
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报