C ++中第Q个人的最大标尺长度
问题陈述
给定数组中n个杆的长度。如果有人捡起任何一根杆，则会分配最长杆的一半（或（max+1）/2），其余部分（最大–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和9，如下所示-
第一人称视角获得最大长度，即12
然后我们从数组中删除12，然后放回（12–1）/2=5
第二人称拿到杆的最大长度即10
然后我们放回（10–1）/2=4
第三人称视角获得最大长度，即9
算法
首先将所有长度分类并推入堆栈
取栈顶元素，除以2，然后将剩余长度推入队列
如果堆栈为空，则弹出前队列并推回队列。如果不是零，则为一半（前/2）
如果队列为空，则从堆栈弹出并推送到队列的一半（顶部/2）（如果非零）
如果两者都不为空，则比较top和front（较大的那个），将其弹出，除以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