โปรแกรม C++ บวกสมาชิกอาร์เรย์จนทุกตัว ≥ k (Min Heap)

บทนำ

กำหนดอาร์เรย์ arr[] และค่า K ต้องการหาจำนวนขั้นตอนน้อยที่สุด ที่บวกสมาชิกสองตัวรวมกัน (แทนที่สองตัวด้วยผลรวม) จนกว่าทุกสมาชิกจะ ≥ K

ตัวอย่าง

arr = {1, 10, 12, 9, 2, 3}, K = 6

1. บวก 1+2=3 → arr = {3, 10, 12, 9, 3}
2. บวก 3+3=6 → arr = {6, 10, 12, 9} → ทุกตัว ≥ 6 เสร็จใน 2 ขั้นตอน

แนวคิด: ใช้ Min Heap

ทุกครั้งดึงค่าน้อยที่สุด 2 ค่ามาบวกกัน (Greedy) ใส่กลับ Heap นับจำนวนครั้ง

ตัวอย่างโค้ด C++ (Min Heap Implementation)

#include <bits/stdc++.h>
using namespace std;

class MinHeap {
    int *harr, capacity, 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 = 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) {
    harr[heap_size] = k;
    int i = heap_size++;
    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) return harr[--heap_size];
    int root = harr[0];
    harr[0] = harr[--heap_size];
    heapify(0);
    return root;
}

void MinHeap::heapify(int i) {
    int l = left(i), r = right(i), 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 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