Cộng các phần tử mảng cho đến khi mọi phần tử đều lớn hơn hoặc bằng k trong C++

Mảng (Array) – Mảng là một bộ chứa các phần tử cùng kiểu dữ liệu, các phần tử được đánh chỉ mục từ 0.

Trong bài toán này, ta sử dụng mảng số nguyên. Kiểm tra xem tất cả các phần tử có lớn hơn số cho trước hay không. Ở đây ta kiểm tra xem tất cả các phần tử của mảng có lớn hơn hoặc bằng một số k cho trước hay không. Nếu không, ta sẽ cộng hai phần tử nhỏ nhất của mảng và coi tổng này như một phần tử đơn lẻ. Sau đó lại kiểm tra điều kiện tương tự cho mảng mới. Nếu điều kiện thỏa mãn, trả về số lần thực hiện phép cộng.

Ví dụ

Mảng = { 2, 6, 3, 12, 7 } K = 5 
Output: 1

Giải thích – Trước tiên kiểm tra xem tất cả các phần tử có lớn hơn hoặc bằng k hay không. Vì không thỏa mãn, ta cộng hai số nhỏ nhất là 2 và 3, phần tử đầu tiên của mảng mới là 5. Kiểm tra lại, lần này điều kiện thỏa mãn nên trả về số lần cộng đã thực hiện.

Thuật toán

Đầu vào – Mảng và K

Bước 1: Kiểm tra xem tất cả các phần tử có lớn hơn hoặc bằng K
Bước 2: Nếu (có) {
    In số lần lặp.
} thoát(0)
Bước 3: Ngược lại {
    Cộng hai phần tử nhỏ nhất của mảng và gộp thành một phần tử.
}
Bước 4: Quay lại bước 1

Ví dụ mã C++

#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; 
}

Kết quả

1