समस्या कथन
एक सरणी में n छड़ की लंबाई को देखते हुए। यदि कोई व्यक्ति किसी भी छड़ को चुनता है, तो सबसे लंबी छड़ का आधा (या (अधिकतम + 1)/2 ) दिया जाता है और शेष भाग (अधिकतम -1) / 2 को वापस रख दिया जाता है। यह माना जा सकता है कि पर्याप्त संख्या में छड़ें हमेशा उपलब्ध होती हैं, एक सरणी q[] में दिए गए M प्रश्नों के उत्तर qith व्यक्ति के लिए उपलब्ध रॉड की सबसे बड़ी लंबाई को खोजने के लिए, बशर्ते qi 1 से शुरू होने वाली एक वैध व्यक्ति संख्या हो
उदाहरण
Input : a[] = {6, 5, 9, 10, 12}
q[] = {1, 3}
Output : 12 9
The first person gets maximum length as 12.
We remove 12 from array and put back (12 -1) / 2 = 5.
Second person gets maximum length as 10.
We put back (10 - 1)/2 which is 4.
Third person gets maximum length as 9. अगर इनपुट ऐरे {6, 5, 9, 10, 12} और
. हैक्वेरी सरणी {1, 3} है तो आउटपुट 12 और 9 के रूप में होगा -
- पहले व्यक्ति को अधिकतम लंबाई यानी 12 की छड़ मिलती है
- फिर हम सरणी से 12 हटाते हैं और वापस रख देते हैं (12 - 1) / 2 =5
- दूसरे व्यक्ति को अधिकतम लंबाई वाली रॉड मिलती है यानी 10
- फिर हम वापस रख देते हैं (10 - 1) / 2 =4
- तीसरे व्यक्ति को अधिकतम लंबाई वाली रॉड मिलती है यानी 9
एल्गोरिदम
- पहले सभी लंबाई को क्रमबद्ध करें और उन्हें एक स्टैक पर पुश करें
- स्टैक का शीर्ष तत्व लें, और 2 से विभाजित करें और शेष लंबाई को कतार में धकेलें
- यदि स्टैक खाली है, तो सामने की कतार को पॉप करें और वापस कतार में धकेलें। यह आधा है (सामने / 2), अगर शून्य नहीं है
- यदि कतार खाली है, तो स्टैक से पॉप करें और कतार में पुश करें, यह आधा है (शीर्ष / 2), यदि शून्य नहीं है
- यदि दोनों खाली नहीं हैं, तो ऊपर और सामने की तुलना करें, जो भी बड़ा हो, उसे 2 से विभाजित करके पीछे धकेल दिया जाना चाहिए
- स्टैक और क्यू दोनों खाली होने पर रुकें
उदाहरण
#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;
} आउटपुट
जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है -
Rod length = 12 10 9 6 6 5 5 4 3 3