Thêm các phần tử của một mảng cho đến khi mọi phần tử trở nên lớn hơn hoặc bằng k trong C ++.

Mảng - Mảng là một vùng chứa các phần tử của cùng một kiểu dữ liệu, các phần tử của chúng được lập chỉ mục bằng 0.

Trong bài toán này, chúng ta sẽ sử dụng một mảng các số nguyên. Và kiểm tra xem tất cả các phần tử có lớn hơn số đã cho hay không. Ở đây chúng ta sẽ kiểm tra xem tất cả các phần tử của mảng có lớn hơn hoặc bằng một số k cho trước hay không. Nếu không thì chúng ta sẽ thêm hai phần tử tối thiểu của mảng và coi tổng này như một phần tử duy nhất. Và sau đó kiểm tra lại điều kiện tương tự cho mảng mới. Nếu điều kiện là đúng thì số lần tổng được thực hiện sẽ được trả về.

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

Giải thích - Đầu tiên chúng ta sẽ kiểm tra xem tất cả các phần tử có lớn hơn k hay không. Vì chúng không phải là chúng, chúng tôi sẽ thêm hai số tối thiểu. Đó là 2 và 3 nên phần tử đầu tiên trong mảng mới của chúng ta sẽ là 5. Bây giờ, chúng ta sẽ kiểm tra lại một lần nữa, lần này điều kiện đã được thỏa mãn nên chúng ta sẽ trả về không. bổ sung mà chúng tôi đã thực hiện.

Thuật toán

Đầu vào - Mảng và 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

Ví dụ

#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;
}

Đầu ra

1