সমস্যা বিবরণ
nটি রডের দৈর্ঘ্য একটি অ্যারেতে দেওয়া আছে। যদি কেউ কোনো রড বেছে নেয়, তবে সবচেয়ে লম্বা রডের অর্ধেক (বা (max + 1) / 2) তাকে দেওয়া হয় এবং বাকি অংশ ((max – 1) / 2) ফিরে রাখা হয়। ধরে নেওয়া হয় যে যথেষ্ট রড সবসময় উপলব্ধ, Mটি কোয়েরি একটি q[] অ্যারেতে দেওয়া আছে, q-তম ব্যক্তির জন্য উপলব্ধ সর্বোচ্চ দৈর্ঘ্যের রড বের করতে হবে, যেখানে qi ১ থেকে শুরু হওয়া একটি বৈধ ব্যক্তি নম্বর।
উদাহরণ
Input : a[] = {6, 5, 9, 10, 12} q[] = {1, 3} Output : 12 9 প্রথম ব্যক্তি সর্বোচ্চ দৈর্ঘ্য ১২ পায়। অ্যারে থেকে ১২ সরিয়ে (12 -1) / 2 = 5 রাখা হয়। দ্বিতীয় ব্যক্তি সর্বোচ্চ দৈর্ঘ্য ১০ পায়। (10 - 1)/2 = 4 রাখা হয়। তৃতীয় ব্যক্তি সর্বোচ্চ দৈর্ঘ্য ৯ পায়।ইনপুট অ্যারে যদি {6, 5, 9, 10, 12} এবং
কোয়েরি অ্যারে {1, 3} হয়, তবে আউটপুট হবে ১২ এবং ৯ −
- প্রথম ব্যক্তি সর্বোচ্চ দৈর্ঘ্যের রড পায় অর্থাৎ ১২
- তারপর ১২ অ্যারে থেকে সরিয়ে (12 – 1) / 2 = 5 রাখা হয়
- দ্বিতীয় ব্যক্তি সর্বোচ্চ দৈর্ঘ্যের রড পায় অর্থাৎ ১০
- তারপর (10 – 1) / 2 = 4 রাখা হয়
- তৃতীয় ব্যক্তি সর্বোচ্চ দৈর্ঘ্যের রড পায় অর্থাৎ ৯
অ্যালগরিদম
- প্রথমে সব দৈর্ঘ্য সোর্ট করে স্ট্যাকে পুশ করুন
- স্ট্যাকের টপ এলিমেন্ট নিন, ২ দিয়ে ভাগ করুন এবং বাকি দৈর্ঘ্য কিউতে পুশ করুন
- যদি স্ট্যাক খালি হয়, তবে কিউর ফ্রন্ট পপ করে আবার কিউতে পুশ করুন। এর অর্ধেক (front / 2), যদি নন-জিরো হয়
- যদি কিউ খালি হয়, তবে স্ট্যাক থেকে পপ করে কিউতে পুশ করুন এর অর্ধেক (top / 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
