C++中第Q个人的最大木棍长度


问题陈述

给定一个数组中n根木棍的长度。如果任何人选择任何一根木棍,则分配最长木棍的一半(或 (max + 1) / 2),并将剩余部分 (max – 1) / 2 放回。可以假设始终有足够的木棍可用,回答数组q[]中给出的M个查询,以找到第q个人的最大可用木棍长度,前提是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,并将剩余长度压入队列。
  • 如果堆栈为空,则弹出队列的头部并压回队列。如果非零,则为其一半 (front / 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

更新于:2020年1月10日

118 次浏览

开始你的职业生涯

完成课程后获得认证

开始
广告