【LeetCode】5698. 构成特定和需要添加的最少元素、

发表于 更新于 分类于 Valine：
本文字数： 65 阅读时长 ≈ 1 分钟

第231场周赛 5698. 构成特定和需要添加的最少元素

思路

  1. 算出原数组与 $goal$ 的差值。
  2. 用 $limit$ 填补这个差值，计算次数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 136 ms
class Solution {
public:
    int minElements(vector<int>& nums, int limit, int goal) {
        int len = nums.size();
        long long int preSum = 0;
        for (int i = 0; i < len; ++i) {
            preSum += nums[ i ];
        }
        int count = 0;
        long long int rest = goal - preSum;
        if ( abs(rest) % limit == 0)
            count = ( abs(rest) / limit );
        else
            count = 1 + ( abs(rest) / limit );
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 212 ms
class Solution {
public:
    int minElements(vector<int>& nums, int limit, int goal) {
        long long s=0;
        for(auto i:nums)
        {
            s+=i;
        }
        long long target=abs(goal-s);
        long long res=0;
        for(int i=limit;i;i--)
        {
            while(target)
            {
                long long temp=0;
                temp=target;
                if(target/i>0)
                {
                    target%=i;
                }
                if(target>=0) res+=temp/i;
                if(target<i)
                {
                    break;
                }
            }
            if(target==0) return res;
        }
        return res;
    }
};