本題為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;
}
}
};
"正是我們每天反復做的事情，最終造就了我們，優秀不是一種行為，而是一種習慣" ---亞里士多德
這里是浙江理工大學22屆ACM集訓隊的成員一枚鴨!
本文首發于博客園，作者：星雙子，除了我自己的轉載請注明原文鏈接：https://www.cnblogs.com/geministar/p/LeetCode1785.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/540141.html
標籤：其他
上一篇：Codeforces Round #838 (Div. 2) D. GCD Queries
下一篇：二叉樹的遍歷