C++에서 모든 요소가 k보다 크거나 같을 때까지 배열 요소를 추가합니다.

배열 − 배열은 동일한 데이터 유형의 요소가 포함된 컨테이너이며 요소의 인덱스는 0입니다.

이 문제에서는 정수 배열을 사용합니다. 그리고 모든 요소가 주어진 숫자보다 큰지 확인하십시오. 여기에서 배열의 모든 요소가 주어진 숫자 k보다 크거나 같은지 확인합니다. 그렇지 않은 경우 배열의 최소 두 요소를 추가하고 이 합계를 단일 요소로 처리합니다. 그런 다음 새 어레이에 대해 동일한 조건을 다시 확인합니다. 조건이 참이면 합계가 수행된 횟수가 반환됩니다.

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

설명 − 먼저 모든 요소가 k보다 크거나 작은지 확인합니다. 그것들이 아니기 때문에 우리는 두 개의 최소 숫자를 추가할 것입니다. 이것은 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