เรามีอาร์เรย์ขององค์ประกอบที่ไม่ได้เรียงลำดับ เช่น arr[] และมีจำนวนเต็ม K และเราต้องหาจำนวนขั้นตอนขั้นต่ำที่จำเป็นในการเพิ่มองค์ประกอบของอาร์เรย์เพื่อให้องค์ประกอบทั้งหมดมีค่ามากกว่าหรือเท่ากับ เค . เราเพิ่มองค์ประกอบของอาร์เรย์ได้ 2 แบบแล้วรวมเป็นหนึ่งเดียว
ตัวอย่าง
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:e 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
