Tìm chiều cao tối đa của kim tự tháp từ mảng đối tượng trong C++

Cho mảng n đối tượng, mỗi đối tượng có độ rộng W[i]. Cần sắp xếp chúng thành hình kim tự tháp thỏa mãn:

• Tổng độ rộng của cấp i nhỏ hơn cấp i+1
• Số lượng đối tượng của cấp i nhỏ hơn cấp i+1

Ví dụ: với trọng lượng [40, 100, 20, 30], kết quả là 2. Cấp trên cùng là 30, cấp dưới là 20, 40 và 100.

Giải thuật tham lam

Sắp xếp mảng tăng dần. Đặt phần tử nhỏ nhất lên đỉnh. Xây dựng các cấp dưới dần với số lượng đối tượng và tổng độ rộng lớn hơn cấp trên.

Ví dụ minh họa

#include <iostream>
#include <algorithm>
using namespace std;

int maxLevelPyramid(int objects[], int n) {
    sort(objects, objects + n);
    
    int levels = 1;
    int prev_width = objects[0];
    int prev_count = 1;
    int curr_width = 0;
    int curr_count = 0;
    
    for (int i = 1; i < n; i++) {
        curr_width += objects[i];
        curr_count++;
        
        if (curr_width > prev_width && curr_count > prev_count) {
            prev_width = curr_width;
            prev_count = curr_count;
            curr_width = curr_count = 0;
            levels++;
        }
    }
    return levels;
}

int main() {
    int boxes[] = {40, 100, 20, 30};
    int n = sizeof(boxes)/sizeof(boxes[0]);
    cout << "Số cấp tối đa của kim tự tháp: " << maxLevelPyramid(boxes, n);
    return 0;
}

Kết quả

Số cấp tối đa của kim tự tháp: 2