本题为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 &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;        }    }};

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

这里是浙江理工大学22届ACM集训队的成员一枚鸭!

本文首发于博客园，作者：星双子，除了我自己的转载请注明原文链接：https://www.cnblogs.com/geministar/p/LeetCode1785.html