程序计算在C ++中应追加多少个数字以创建从1到k的所有数字

假设我们有一个称为nums的数字列表，另一个值为k。我们必须找到需要插入到num中的最小数量的数字，以便我们可以使用num中的某些子集从[1，k]中得出任何数字。

因此，如果输入类似于nums = [3，5]，k = 6，则输出将为2，因为我们必须插入1、2，所以我们可以使：1 = [1]，2 = [2 ]，3 = [3]，4 = [1、3]，5 = [5]，6 = [1、5]。

为了解决这个问题，我们将遵循以下步骤-

• 对数组数字进行排序

• sum：= 0，下一个：= 1，ret：= 0

• 对于我所有的数字

• 从循环中出来

• 如果总和> = k，则：

• 总和：=总和+下一个

• 下一个：= sum + 1

• （增加ret 1）

• 从循环中出来

• 而下一个<i，请执行：

• 如果总和> = k，则：

• 和：=和+ i

• 下一个：= sum + 1

• 而下一个<= k，请执行以下操作：

• 总和：=总和+下一个

• 下一个：= sum + 1

• （增加ret 1）

• 返回ret

让我们看下面的实现以更好地理解-

示例

#include
using namespace std;
class Solution {
   public:
   int solve(vector& nums, int k) {
      sort(nums.begin(), nums.end());
      int sum = 0;
      int next = 1;
      int ret = 0;
      for (int i : nums) {
         while (next < i) {
            if (sum >= k) break;
            sum += next;
            next = sum + 1;
            ret++;
         }
         if (sum >= k) break;
         sum += i;
         next = sum + 1;
      }
      while (next <= k) {
         sum += next;
         next = sum + 1;
         ret++;
      }
      return ret;
   }
};

int solve(vector& nums, int k) {
   return (new Solution())->solve(nums, k);
}

int main(){
   vector v = {3, 5};
   int k = 6;
   cout << solve(v, k);
}

输入值

[3, 5], 6

输出结果

2