「贪心」构成特定和需要添加的最少元素(力扣第1785题)

本题为12月16日力扣每日一题

题目来源:力扣第1785题

题目tag:贪心

题面

题目描述

给你一个整数数组nums，和两个整数limit与goal。数组nums有一条重要属性：abs(nums[i]) <= limit 。

返回使数组元素总和等于goal所需要向数组中添加的最少元素数量，添加元素不应改变数组中abs(nums[i]) <= limit这一属性。

注意，如果x >= 0，那么abs(x)等于x；否则，等于-x。

示例

示例 1

输入：

nums = [1,-1,1], limit = 3, goal = -4

输出：

2

解释：

可以将-2和-3添加到数组中，数组的元素总和变为1 - 1 + 1 - 2 - 3 = -4。

示例 2

输入：

nums = [1,-10,9,1], limit = 100, goal = 0

输出：

1

提示

1 <= nums.length <= 105
1 <= limit <= 106
-limit <= nums[i] <= limit
-109 <= goal <= 109

思路分析

一道简单的思维题.

先考虑当前总和(下记为sum)小于goal的情况,此时需要添加一些正数,来填满中间的差.显然应该贪心地每次均填limit,这样可以保证每次填得最多,使得填的次数最少.如果最后恰好放满了,答案即为(goal - sum) / limit.当然,有可能会出现最后一次不够limit,这时只填剩下的差即可,此时答案即为(goal - sum) / limit + 1.

接着考虑sum大于goal的情况,此时需要添加一些负数,来砍掉多出的部分.显然应该贪心地每次砍limit(放入-limit),这样可以保证每次砍得最多,使砍的次数最少.如果最后恰好砍完了,答案即为(sum - goal) / limit.当然,有可能会出现最后一次砍limit太多,这时只砍掉剩下的多出来的部分即可,此时答案即为(sum - goal) / limit + 1.

综上,直接用|goal - sum|作为差值即可统一上面两种情况,得出最后的答案.

参考代码

class Solution
{
public:
    int minElements(vector<int> &nums, int limit, int goal)
    {
        // 求和
        long long sum = 0;
        for (auto i : nums)
        {
            sum += i;
        }

        // 计算差,利用绝对值排除正负干扰(由于个人学校的oj中的abs存在bug,所以个人习惯用fabs取绝对值)
        long long diff = fabs(goal - sum);

        // 分类计算需要几个数
        if (diff % limit == 0)
        {
            return diff / limit;
        }
        else
        {
            return diff / limit + 1;
        }
    }
};

"正是我们每天反复做的事情，最终造就了我们，优秀不是一种行为，而是一种习惯" ---亚里士多德