すべての要素がk以上になるまで配列の要素を追加するC++プログラム

ソートされていない要素の配列、つまりarr []があり、整数Kがあり、すべての要素を以上にするために配列の要素を追加するために必要な最小ステップ数を見つける必要があります。 K 。配列の2つの要素を追加して、それらを1つにすることができます。

例

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 つまり、 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;
}

出力

2