อาร์เรย์ − อาร์เรย์คือคอนเทนเนอร์ของอิลิเมนต์ที่มีประเภทข้อมูลเดียวกัน ซึ่งอิลิเมนต์จะถูกจัดทำดัชนีเป็น 0
ในปัญหานี้ เราจะใช้อาร์เรย์ของจำนวนเต็ม และตรวจสอบว่าองค์ประกอบทั้งหมดมากกว่าจำนวนที่กำหนดหรือไม่ ที่นี่เราจะตรวจสอบว่าองค์ประกอบทั้งหมดของอาร์เรย์มากกว่าหรือเท่ากับจำนวนที่กำหนด k หรือไม่ ถ้าไม่เช่นนั้น เราจะเพิ่มองค์ประกอบขั้นต่ำสองรายการของอาร์เรย์และถือว่าผลรวมนี้เป็นองค์ประกอบเดียว จากนั้นตรวจสอบเงื่อนไขเดียวกันอีกครั้งสำหรับอาร์เรย์ใหม่ หากเงื่อนไขเป็นจริง จำนวนครั้งที่ดำเนินการรวมจะถูกส่งคืน
Array = { 2, 6,3,12, 7} K = 5
Output : 1 คำอธิบาย − ก่อนอื่นเราจะตรวจสอบว่าองค์ประกอบทั้งหมดมากกว่าหรือ k หรือไม่ เนื่องจากไม่ใช่ เราจะเพิ่มตัวเลขขั้นต่ำสองตัว ซึ่งก็คือ 2 และ 3 ดังนั้นองค์ประกอบแรกในอาร์เรย์ใหม่ของเราจะเป็น 5 ตอนนี้ เราจะตรวจสอบอีกครั้ง คราวนี้เป็นไปตามเงื่อนไข ดังนั้นเราจะส่งคืนหมายเลข ของการเพิ่มเติมที่เราทำ
อัลกอริทึม
ป้อนข้อมูล − Array และ 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;
} ผลลัพธ์
1
