Chương trình C++ cộng phần tử mảng cho đến khi tất cả ≥ K

Cho mảng arr[] và số K. Mỗi phép toán: chọn 2 phần tử, cộng lại thành 1 phần tử (thay thế 2 phần tử cũ). Tìm số phép tối thiểu để mọi phần tử ≥ K.

Ví dụ: arr={1,10,12,9,2,3}, K=6. B1: 1+2=3 -> {3,10,12,9,3}. B2: 3+3=6 -> {6,10,12,9}. Tất cả ≥6. Kết quả: 2 phép.

Giải pháp: Min-Heap (Priority Queue). Luôn lấy 2 phần tử nhỏ nhất, cộng lại, đẩy vào heap. Lặp cho đến khi min ≥ K.

Ví dụ code (tự cài MinHeap)

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

class MinHeap {
    int *harr, capacity, heap_size;
    void heapify(int i);
public:
    MinHeap(int arr[], int n);
    int extractMin();
    void insertKey(int k);
    int getMin() { return harr[0]; }
    int getSize() { return heap_size; }
};

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::heapify(int i) {
    int l = 2*i+1, r = 2*i+2, smallest = i;
    if (l < heap_size && harr[l] < harr[smallest]) smallest = l;
    if (r < heap_size && harr[r] < harr[smallest]) smallest = r;
    if (smallest != i) { swap(harr[i], harr[smallest]); heapify(smallest); }
}

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::insertKey(int k) {
    harr[heap_size] = k;
    int i = heap_size++;
    while (i && harr[(i-1)/2] > harr[i]) {
        swap(harr[i], harr[(i-1)/2]);
        i = (i-1)/2;
    }
}

int countMinOps(int arr[], int n, int k) {
    MinHeap h(arr, n);
    int res = 0;
    while (h.getMin() < k) {
        if (h.getSize() == 1) return -1; // không thể
        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 << "So phep toi thieu: " << countMinOps(arr, n, k);
    return 0;
}

Kết quả

So phep toi thieu: 2