C++でのQ人目のロッドの最大長

問題の説明

アレイ内のn本のロッドの長さが与えられます。誰かがロッドを選ぶと、最も長いロッドの半分（または（max + 1）/ 2）が割り当てられ、残りの部分（max – 1）/2が戻されます。十分な数のロッドが常に利用可能であると想定できます。qiが1から始まる有効な人物番号である場合、配列q []で指定されたMクエリに答えて、q番目の人物が利用できるロッドの最大長を見つけます。

例

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のロッドを取得します
• 次に、配列から12を削除し、（12 – 1）/ 2=5に戻します
• 2人目は、最大長、つまり10のロッドを取得します
• 次に、（10 – 1）/ 2=4を戻します
• 3人目は、最大長、つまり9のロッドを取得します

アルゴリズム

• 最初にすべての長さを並べ替えて、スタックにプッシュします
• スタックの一番上の要素を取得し、2で割り、残りの長さをキューにプッシュします
• スタックが空の場合は、フロントキューをポップして、キューにプッシュバックします。ゼロ以外の場合は半分（フロント/ 2）
• キューが空の場合は、スタックからポップして、ゼロ以外の場合は半分（top / 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