题解-英雄的力量

Problem: 2681. 英雄的力量

• 思路
• 解题方法
• Code

思路

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

解题方法

1. 确定了子序列的最大值之后,我们只需要确定子序列里面各个值最小值出现了几次
2. 也就是确定排序后的必选且为最大值时,我们假设此时在答案中与除自身之外他的平方相乘的所有值之和为,此时有答案
3. 不去管现在为多少,我们假设现在要选取的是为最大值,则注意到对于子序列
   1. 如果不选,也会和相乘
   2. 如果选取,对于所有不是最小值的情况,也会和相乘,而是最小值的情况只有一个(也就是选取和两个)
4. 根据以上的两个推理,我们能够得出,既

• 时间复杂度
• 空间复杂度

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))%mod
            pre=(pre*2+num)%mod
        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*num%mod)*(pre+num))%mod;
            pre=(pre*2+num)%mod;
        }
        return res;
    }
};