모든 요소가 k보다 크거나 같을 때까지 배열 요소를 추가하는 C++ 프로그램

<시간/>

정렬되지 않은 요소, 즉 arr[]의 배열이 있고 정수 K가 있으며 모든 요소를 보다 크거나 같게 만들기 위해 배열의 요소를 추가하는 데 필요한 최소 단계 수를 찾아야 합니다. K . 배열의 두 요소를 추가하여 하나로 만들 수 있습니다.

예

Input: arr[] = {1 10 12 9 2 3},K = 6
Output: 2

설명

먼저 (1 + 2)를 추가할 수 있습니다. , 따라서 새 배열은 3 10 12 9 3입니다. , (3 + 3)을 추가할 수 있습니다. , 따라서 새 배열은 6 10 12 9입니다. , 목록의 모든 요소가 6보다 크다는 것을 알 수 있습니다. . 따라서 출력은

2 i:2 이를 위해서는 작업이 필요합니다.

예시

#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 countMinOps(int arr[], int n, int k) {
   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++;
   }
   return res;
}
int main() {
   int arr[] = {1, 10, 12, 9, 2, 3};
   int n = sizeof(arr)/sizeof(arr[0]);
   int k = 6;
   cout << countMinOps(arr, n, k);
   return 0;
}