การบวกสมาชิกอาร์เรย์จนทุกตัวมากกว่าหรือเท่ากับ K ใน C++

อาร์เรย์ (Array) คือตัวเก็บข้อมูลชนิดเดียวกันที่จัดดัชนีเริ่มจาก 0

ในปัญหานี้ เราจะใช้อาร์เรย์ของจำนวนเต็ม และตรวจสอบว่าสมาชิกทุกตัวมีค่ามากกว่าหรือเท่ากับตัวเลขที่กำหนด k หรือไม่ หากไม่ เราจะนำสองตัวที่มีค่าน้อยที่สุดมาบวกกัน และนำผลรวมมาเป็นสมาชิกใหม่หนึ่งตัว จากนั้นตรวจสอบเงื่อนไขเดิมกับอาร์เรย์ใหม่ หากเงื่อนไขเป็นจริง เราจะส่งคืนจำนวนครั้งที่ทำการบวก

Array = {2, 6, 3, 12, 7}, K = 5
Output: 1

คำอธิบาย - ก่อนอื่นตรวจสอบว่าสมาชิกทุกตัว >= k หรือไม่ เนื่องจากไม่ผ่าน เราจึงบวกสองตัวที่น้อยที่สุดคือ 2 และ 3 ได้ 5 ตอนนี้ตรวจสอบอีกครั้ง เงื่อนไขเป็นจริง จึงส่งคืนจำนวนครั้งที่บวก = 1

อัลกอริทึม

Input - อาร์เรย์และค่า K

ขั้นตอนที่ 1: ตรวจสอบว่าสมาชิกทุกตัว >= K
ขั้นตอนที่ 2: ถ้าใช่ { พิมพ์จำนวนรอบการทำงาน } จบโปรแกรม
ขั้นตอนที่ 3: ไม่ใช่ { บวกสองตัวที่น้อยที่สุดของอาร์เรย์และรวมเป็นหนึ่งตัว }
ขั้นตอนที่ 4: กลับไปขั้นตอนที่ 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