题解-英雄的力量

Problem: 2681. 英雄的力量

题目描述

给你一个下标从0开始的整数数组nums，它表示英雄的能力值。如果我们选出一部分英雄，这组英雄的力量定义为：

• i0 ，i1 ，… ik 表示这组英雄在数组中的下标。那么这组英雄的力量为 max(nums[i0],nums[i1] ... nums[ik])2 * min(nums[i0],nums[i1] ... nums[ik]) 。

请你返回所有可能的非空英雄组的力量之和。由于答案可能非常大，请你将结果对109 + 7取余。

思路

• 选取与顺序无关先排序
• 接下来只要枚举所有子序列的最大值的平方和最小值的乘积之和
• 注意到只和最大值和最小值有关

解题方法

1. 确定了子序列的最大值之后,我们只需要确定子序列里面各个值最小值出现了几次
2. 也就是确定排序后的$nums[i]$必选且为最大值时,我们假设此时在答案中与除自身之外他的平方相乘的所有值之和为$pre_i$,此时有答案$res_i=nums[i]^2*(pre_i+nums[i])$
3. 不去管$pre_i$现在为多少,我们假设现在要选取的是$nums[i+1]$为最大值,则注意到对于子序列
   1. 如果不选$ nums[i] $,$ pre_i$也会和$nums[i+1]$相乘
   2. 如果选取$nums[i]$,对于所有$nums[i]$不是最小值的情况,$pre_i$也会和$nums[i+1]$相乘,而$nums[i]$是最小值的情况只有一个(也就是选取$i$和$i+1$两个)
4. 根据以上的两个推理,我们能够得出 $$ \displaystyle res_{i+1}=nums[i+1]^2 \cdot (pre_i \cdot 2+nums[i]+nums[i+1]) \\ pre_{i+1}=pre_i\cdot 2+nums[i] $$
5. $res=\displaystyle\sum^{n}_{i=0} res_i $

• 时间复杂度$O(nlogn)$
• 空间复杂度$O(1)$

Code

class Solution:
    def sumOfPower(self, nums: List[int]) -> int:
        mod=1000000007
        nums.sort()
        pre=0
        res=0
        for num in nums:
            res=(res+(pre+num)*(num**2)
            pre=(pre*2+num
        return res

class Solution {
public:
    int sumOfPower(vector<int>& nums) {
        const int mod=1e9+7;
        sort(nums.begin(),nums.end());
        int res=0,pre=0;
        for (long num:nums){
            res=(res+(num*nu
            pre=(pre*2+num
        }
        return res;
    }
};