Chúng ta có mảng phần tử chưa được sắp xếp, tức là arr [] và có số nguyên K, và chúng ta phải tìm số bước tối thiểu cần thiết trong đó các phần tử của mảng sẽ được thêm vào để làm cho tất cả các phần tử lớn hơn hoặc bằng K . Chúng ta có thể thêm hai phần tử của mảng và biến chúng thành một.
Ví dụ,
Input: arr[] = {1 10 12 9 2 3},K = 6
Output: 2 Giải thích
Trước tiên, chúng ta có thể thêm (1 + 2) , vì vậy mảng mới là 3 10 12 9 3 , chúng tôi có thể thêm (3 + 3) , Vì vậy, mảng mới là 6 10 12 9 , chúng tôi có thể biết rằng tất cả các phần tử trong danh sách đều lớn hơn 6 . Do đó đầu ra là
2 i:đ 2 cần có các thao tác để thực hiện việc này.
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 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;
} Đầu ra
2