Độ dài que lớn nhất cho người thứ Q trong C++

Đề bài

Cho độ dài n que trong mảng. Nếu người nào đó chọn que nào, nửa que dài nhất (hoặc (max + 1) / 2) được giao cho người đó và phần còn lại (max - 1) / 2 được đặt lại. Giả sử luôn có đủ que, trả lời M truy vấn trong mảng q[] để tìm độ dài que lớn nhất cho người thứ q_i (q_i là số người hợp lệ bắt đầu từ 1).

Ví dụ

Input: a[] = {6, 5, 9, 10, 12}, q[] = {1, 3}
Output: 12 9

Người 1 nhận que dài nhất 12. Loại 12, đặt lại (12-1)/2 = 5.
Người 2 nhận que dài nhất 10. Đặt lại (10-1)/2 = 4.
Người 3 nhận que dài nhất 9.

Thuật toán

1. Sắp xếp tất cả độ dài và đẩy vào stack
2. Lấy phần tử đỉnh stack, chia 2 và đẩy phần còn lại vào queue
3. Nếu stack rỗng: lấy front queue, đẩy lại queue nửa của nó (nếu khác 0)
4. Nếu queue rỗng: lấy từ stack, đẩy vào queue nửa của nó (nếu khác 0)
5. Nếu cả hai đều không rỗng: so sánh top stack và front queue, lấy cái lớn hơn, chia 2, đẩy lại
6. Dừng khi cả stack và queue đều rỗng

Chương trình C++

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

vector<int> getMaxRodLength(int *arr, int n, int m) {
    queue<int> q;
    sort(arr, arr + n);
    stack<int> s;
    
    for (int i = 0; i < n; ++i)
        s.push(arr[i]);
    
    vector<int> result;
    
    while (!s.empty() || !q.empty()) {
        int val;
        if (q.empty()) {
            val = s.top();
            result.push_back(val);
            s.pop();
            val = val / 2;
            if (val) q.push(val);
        } else if (s.empty()) {
            val = q.front();
            result.push_back(val);
            q.pop();
            val = val / 2;
            if (val != 0) q.push(val);
        } else {
            val = s.top();
            int fr = q.front();
            if (fr > val) {
                result.push_back(fr);
                q.pop();
                fr = fr / 2;
                if (fr) q.push(fr);
            } else {
                result.push_back(val);
                s.pop();
                val = val / 2;
                if (val) q.push(val);
            }
        }
    }
    return result;
}

int main() {
    int rods = 5;
    int queries = 10;
    int arr[rods] = {6, 5, 9, 10, 12};
    vector<int> result = getMaxRodLength(arr, rods, queries);
    int query[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int n_query = sizeof(query) / sizeof(query[0]);
    
    cout << "Rod length = ";
    for (int i = 0; i < n_query; ++i)
        cout << result[query[i] - 1] << " ";
    cout << endl;
    return 0;
}

Kết quả

Rod length = 12 10 9 6 6 5 5 4 3 3