在C ++中添加数组元素，直到每个元素都大于或等于k。

Z时代
2024-01-10
分类：综合

数组-数组是具有相同数据类型的元素的容器，其元素的索引为0。

在这个问题中，我们将使用整数数组。并检查所有元素是否都大于给定数目。在这里，我们将检查数组的所有元素是否都大于或等于给定的数k。如果不是，那么我们将添加数组的两个最小元素，并将此总和视为单个元素。然后再次检查新数组的相同条件。如果条件成立，则返回求和的次数。

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

解释-首先，我们将检查所有元素是否大于或等于k。由于不是，我们将添加两个最小值。这是2和3，所以新数组中的第一个元素将是5。现在，再次检查，这次条件已满足，因此将返回否。我们所做的补充。

算法

输入-数组和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;
}