44.最大边权和

题目概述

题目详情(点我)

现在有n个点(1<=n<=1000)，每个点都有一个值称为点权ai(ai为偶数，1<=ai<=1000)，现在可以将任意两个点相连，连起来以后这条边也有一个值称为边权，这个边的边权为这两个点的点权之和的一半。现在需要你添加n-1条边，问将这n个点连通以后(连通是指任意两个点都能互相到达)的最大的边权和是多少。

输入:
输入点的数量n；和n个数，表示点权的值

输出:
输出最大的边权和

题解

解题方法

• 贡献最大值

算法知识

• 贪心算法

  • 时间复杂度: n
  • 空间复杂度: 1

解题思路

审题

• int n : n个点
• int[] nums : 存储n个点的权值
• 边权 = 两个点权值的和的一半
• 添加n-1条边

题目要求

• 求最大边权和

思路

• 只有n-1条边, 就想要让边权和最大

  • n-1条边: 每个点都得找另外一个点相连接
  • 为了让边权变得最大, 就只能找最大权值的点进行连接

• 题目要求转换:

  1. 查找最大权值的点
  2. 除最大权值的点外其余的点 与 最大权值点相加的总和的一半

步骤

1. 定义变量

   • int result, 用来存储最终结果, 初始化为0
   • int max, 用来存储最大值, 初始化为0
   • int index, 用来存储最大值的索引, 初始化为-1

2. 循环遍历nums数组, 获取最大值

   • 如果nums[i] > max, 则更新最大值max, 同时更新最大值索引index

3. 循环遍历nums数组, 让除了最大值外的每个值与最大值求边权

   • 如果是索引等于最大值索引, 则直接跳过, 因为没法和自己求边权值
   • 用result累加边权值
4. 返回最大边权值