C ++では、すべての要素がk以上になるまで配列の要素を追加します。

配列 −配列は、同じデータ型の要素のコンテナであり、その要素のインデックスは0です。

この問題では、整数の配列を使用します。そして、すべての要素が指定された数より大きいかどうかを確認します。ここでは、配列のすべての要素が指定された数k以上であるかどうかを確認します。そうでない場合は、配列の2つの最小要素を追加し、この合計を1つの要素として扱います。次に、新しいアレイの同じ条件を再度確認します。条件が真であることが判明した場合、合計が実行された回数が返されます。

Array = { 2, 6,3,12, 7} K = 5
Output : 1

説明 −最初に、すべての要素がkより大きいかどうかを確認します。そうではないので、2つの最小数を追加します。これは2と3なので、新しい配列の最初の要素は5になります。ここでもう一度確認します。今回は条件が満たされているため、noを返します。私たちが行った追加の数。

アルゴリズム

入力 −配列とK

Step 1 : check if all elements are greater than or equal to K
Step 2: if(yes){
   Print number of iterations.
}
exit(0)
Step 3: else {
   Add smallest two elements of the array and make it one element.
}
Step 4: goto step 1

例

#include<bits/stdc++.h>
using namespace std;
class MinHeap{
   int *harr;
   int capacity;
   int heap_size;
   public:
   MinHeap(int *arr, int capacity);
   void heapify(int );
   int parent(int i){
      return (i-1)/2;
   }
   int left(int i){
      return (2*i + 1);
   }
   int right(int i){
      return (2*i + 2);
   }
   int extractMin();
   int getMin(){
      return harr[0];
   }
   int getSize(){
      return heap_size;
   }
   void insertKey(int k);
};
MinHeap::MinHeap(int arr[], int n){
   heap_size = n;
   capacity = n;
      harr = new int[n];
   for (int i=0; i<n; i++)
      harr[i] = arr[i];
   for (int i=n/2-1; i>=0; i--)
      heapify(i);
}
void MinHeap::insertKey(int k){
   heap_size++;
   int i = heap_size - 1;
   harr[i] = k;
   while (i != 0 && harr[parent(i)] > harr[i]){
      swap(harr[i], harr[parent(i)]);
      i = parent(i);
   }
}
int MinHeap::extractMin(){
   if (heap_size <= 0)
      return INT_MAX;
   if (heap_size == 1){
      heap_size--;
      return harr[0];
   }
   int root = harr[0];
   harr[0] = harr[heap_size-1];
   heap_size--;
   heapify(0);
   return root;
}
void MinHeap::heapify(int i){
   int l = left(i);
   int r = right(i);
   int smallest = i;
   if (l < heap_size && harr[l] < harr[i])
      smallest = l;
   if (r < heap_size && harr[r] < harr[smallest])
      smallest = r;
   if (smallest != i){
      swap(harr[i], harr[smallest]);
      heapify(smallest);
   }
}
int main(){
   int arr[] = { 2, 6,3,12, 7};
   int n = sizeof(arr)/sizeof(arr[0]);
   int k = 5;
   MinHeap h(arr, n);
   long int res = 0;
   while (h.getMin() < k){
      if (h.getSize() == 1)
         return -1;
      int first = h.extractMin();
      int second = h.extractMin();
      h.insertKey(first + second);
      res++;
   }
   cout << res;
   return 0;
}

出力

1