golang刷leetcode：道路的最大總重要性

給你一個整數(shù) n ，表示一個國家里的城市數(shù)目。城市編號為 0 到 n - 1 。

給你一個二維整數(shù)數(shù)組 roads ，其中 roads[i] = [ai, bi] 表示城市 ai 和 bi 之間有一條 雙向 道路。

你需要給每個城市安排一個從 1 到 n 之間的整數(shù)值，且每個值只能被使用 一次 。道路的 重要性 定義為這條道路連接的兩座城市數(shù)值 之和 。

請你返回在最優(yōu)安排下，所有道路重要性 之和 最大 為多少。

示例 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

• 沒有重復(fù)道路。

解題思路：

1，本題的關(guān)鍵在于如何給每個節(jié)點安排值

2，如果要和最大，需要把值最大的節(jié)點計算更多次

3，因此我們統(tǒng)計每個節(jié)點的度

4，一個節(jié)點的值被計算的次數(shù)就是它的度

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)}

推薦閱讀

• golang刷leetcode：公平分發(fā)餅干