সমস্যা বিবৃতি
একটি অ্যারের মধ্যে n রডের দৈর্ঘ্য প্রদত্ত। কোনো ব্যক্তি কোনো রড বাছাই করলে, দীর্ঘতম রডের অর্ধেক (অথবা (সর্বোচ্চ + 1) / 2 ) বরাদ্দ করা হয় এবং অবশিষ্ট অংশ (সর্বোচ্চ - 1) / 2 ফিরিয়ে দেওয়া হয়। এটা ধরে নেওয়া যেতে পারে যে পর্যাপ্ত সংখ্যক রড সর্বদা উপলব্ধ থাকে, qith ব্যক্তির জন্য উপলব্ধ রডের বৃহত্তম দৈর্ঘ্য খুঁজে বের করতে একটি অ্যারে q[]-এ দেওয়া M প্রশ্নের উত্তর দিন, তবে শর্ত থাকে যে 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 – 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
