C++で1からkまでのすべての数値を作成するために追加する必要のある数値の数をカウントするプログラム

numsと呼ばれる数値のリストと別の値kがあるとします。 numsのサブセットを使用して、[1、k]から任意の数を作成できるように、numsに挿入する必要のある最小数を見つける必要があります。

したがって、入力がnums =[3、5]、k =6の場合、出力は2になります。これは、1、2を挿入する必要があるため、次のようになります。1 =[1]、2 =[2 ]、3 =[3]、4 =[1、3]、5 =[5]、6 =[1、5]。

これを解決するには、次の手順に従います-

• 配列番号を並べ替える
• sum：=0、next：=1、ret：=0
• すべてのiの数
  • 次の
  • 合計>=kの場合、次のようになります。
    • ループから抜け出す
  • 合計：=合計+次
  • 次：=合計+ 1
  • （retを1増やします）
• 合計>=kの場合、次のようになります。
  • ループから抜け出す
• sum：=sum + i
• 次：=合計+ 1

理解を深めるために、次の実装を見てみましょう-

例

#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