算法筆試模拟題精解之“最大邊權和”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

https://developer.aliyun.com/coding

本文為大家介紹其中的 第44題：最大邊權和 的題目解析，具體如下：

題目描述

題目等級：容易

知識點：貪心

檢視題目：最大邊權和

現在有n個點(1<=n<=1000)，每個點都有一個值稱為點權ai(ai為偶數，1<=ai<=1000)，現在可以将任意兩個點相連，連起來以後這條邊也有一個值稱為邊權，這個邊的邊權為這兩個點的點權之和的一半。現在需要你添加n-1條邊，問将這n個點連通以後(連通是指任意兩個點都能互相到達)的最大的邊權和是多少?

輸入點的數量n；和n個數，表示點權的值

輸出最大的邊權和

示例1

輸入：

5

[2,4,6,8,10]

輸出：

30

解題思路：貪心

根據題意，最終需要将n個點連通并達到最大邊權，而邊權為兩個點的點權之和的一半，是以一個點加入連通圖的最大邊權就是和點權最大的點連通。

是以想要得到最大邊權和，隻要所有點都與點權最大的點相連即可。

實作過程中，首先求出最大的點權，然後計算出其他點與這個權值最大的點的邊權之和即可。

時間複雜度：O(n)

空間複雜度：O(1)

看完之後是不是有了想法了呢，快來練練手吧>>