C++ में Qवें व्यक्ति के लिए छड़ की अधिकतम लंबाई

समस्या कथन

एक ऐरे में n छड़ों की लंबाई दी गई है। यदि कोई व्यक्ति कोई छड़ चुनता है, तो सबसे लंबी छड़ का आधा भाग (या (max + 1) / 2) असाइन किया जाता है और शेष भाग (max - 1) / 2 वापस रख दिया जाता है। यह मान लिया जा सकता है कि पर्याप्त संख्या में छड़ें हमेशा उपलब्ध हैं, M क्वेरी का उत्तर दें जो एक ऐरे q[] में दी गई हैं ताकि qवें व्यक्ति के लिए उपलब्ध सबसे बड़ी छड़ की लंबाई ढूंढी जा सके, बशर्ते qi 1 से शुरू होने वाली एक वैध व्यक्ति संख्या हो।

उदाहरण

इनपुट: a[] = {6, 5, 9, 10, 12}   q[] = {1, 3} 
आउटपुट: 12 9 
पहला व्यक्ति अधिकतम लंबाई 12 प्राप्त करता है। हम ऐरे से 12 हटाते हैं और (12 - 1) / 2 = 5 वापस रखते हैं। 
दूसरा व्यक्ति अधिकतम लंबाई 10 प्राप्त करता है। हम (10 - 1)/2 वापस रखते हैं जो 4 है। 
तीसरा व्यक्ति अधिकतम लंबाई 9 प्राप्त करता है।

यदि इनपुट ऐरे {6, 5, 9, 10, 12} है और

क्वेरी ऐरे {1, 3} है तो आउटपुट 12 और 9 होगा -

• पहला व्यक्ति अधिकतम लंबाई वाली छड़ प्राप्त करता है यानी 12
• फिर हम ऐरे से 12 हटाते हैं और (12 - 1) / 2 = 5 वापस रखते हैं
• दूसरा व्यक्ति अधिकतम लंबाई वाली छड़ प्राप्त करता है यानी 10
• फिर हम (10 - 1) / 2 = 4 वापस रखते हैं
• तीसरा व्यक्ति अधिकतम लंबाई वाली छड़ प्राप्त करता है यानी 9

एल्गोरिदम

• सभी लंबाई को सॉर्ट करें और उन्हें स्टैक पर पुश करें
• स्टैक के शीर्ष तत्व को लें, और 2 से विभाजित करें और शेष लंबाई को कतार में पुश करें
• यदि स्टैक खाली है, तो कतार के सामने को पॉप करें और वापस कतार में पुश करें। इसका आधा (front / 2), यदि शून्येतर है
• यदि कतार खाली है, तो स्टैक से पॉप करें और कतार में पुश करें इसका आधा (top / 2), यदि शून्येतर है
• यदि दोनों खाली नहीं हैं, तो शीर्ष और सामने की तुलना करें, जो भी बड़ा हो उसे पॉप करें, 2 से विभाजित करें और फिर वापस पुश करें
• जब दोनों स्टैक और कतार खाली हो जाएं तो रुकें

उदाहरण

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

vector getMaxRodLength(int* arr, int n, int m) {
    queue q;
    sort(arr, arr + n);
    stack s;
    
    for (int i = 0; i < n; ++i) {
        s.push(arr[i]);
    }
    
    vector 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 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;
}

आउटपुट

जब आप उपरोक्त प्रोग्राम को कंपाइल और निष्पादित करते हैं। यह निम्न आउटपुट उत्पन्न करता है -

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