線上程式設計-44最大邊權和

題目

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

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

輸出最大的邊權和

分析

拿到這個題目，個人了解，總共有以下要點：

• 所有點全部連通：意味着所有數字要使用一遍
• 添加n-1條邊：控制上限
• 邊權為這兩個點的點權之和的一半：意味着兩個點數值越大，則邊權越大；

通過以上，可以得出，所有點均和最大點做比對，則能拿到最大的邊權和

而1<=n<=1000，則應該分類讨論

• n=1：無邊，是以為0
• n=2：兩數之和/2
• 其他：sum = (max*(n-2）+n個點之和)/2

源碼

詳細源碼見

https://code.aliyun.com/xinYe/aliProgrammaCode.git